The structure of translational tilings in ${\mathbb{Z}}^d$

Abstract

We obtain structural results on translational tilings of periodic functions in ${\mathbb{Z}}^d$ by finite tiles. In particular, we show that any level one tiling of a periodic set in ${\mathbb{Z}}^2$ must be weakly periodic (the disjoint union of sets that are individually periodic in one direction), but present a counterexample of a higher level tiling of ${\mathbb{Z}}^2$ that fails to be weakly periodic. We also establish a quantitative version of the two-dimensional periodic tiling conjecture which asserts that any finite tile in ${\mathbb{Z}}^2$ that admits a tiling, must admit a periodic tiling, by providing a polynomial bound on the period; this also gives an exponential-type bound on the computational complexity of the problem of deciding whether a given finite subset of ${\mathbb{Z}}^2$ tiles or not. As a byproduct of our structural theory, we also obtain an explicit formula for a universal period for all tilings of a one-dimensional tile.

References in corpus (3)

• Spectrality and tiling by cylindric domains
• On non-periodic tilings of the real line by a function
• Tiling by translates of a function: results and open problems

Cited by in corpus (1)

• Undecidable translational tilings with only two tiles, or one nonabelian tile