Undecidable translational tilings with only two tiles, or one nonabelian tile
Preprint
Abstract
We construct an example of a group $G = \mathbb{Z}^2 \times G_0$ for a finite abelian group $G_0$, a subset $E$ of $G_0$, and two finite subsets $F_1,F_2$ of $G$, such that it is undecidable in ZFC whether $\mathbb{Z}^2\times E$ can be tiled by translations of $F_1,F_2$. In particular, this implies that this tiling problem is aperiodic, in the sense that (in the standard universe of ZFC) there exist translational tilings of $E$ by the tiles $F_1,F_2$, but no periodic tilings. Previously, such aperiodic or undecidable translational tilings were only constructed for sets of eleven or more tiles (mostly in $\mathbb{Z}^2$). A similar construction also applies for $G = \mathbb{Z}^d$ for sufficiently large $d$. If one allows the group $G_0$ to be non-abelian, a variant of the construction produces an undecidable translational tiling with only one tile $F$. The argument proceeds by first observing that a single tiling equation is able to encode an arbitrary system of tiling equations, which in turn can encode an arbitrary system of certain functional equations once one has two or more tiles. In particular, one can use two tiles to encode tiling problems for an arbitrary number of tiles.
Keywords
All Related Versions
This publication has 23 references indexed in Scilit:
- A Small Aperiodic Set of Planar TilesEuropean Journal of Combinatorics, 1999
- Deterministic Aperiodic Tile SetsGeometric and Functional Analysis, 1999
- A small aperiodic set of Wang tilesDiscrete Mathematics, 1996
- Tiling the line with translates of one tileInventiones Mathematicae, 1996
- An aperiodic set of Wang cubes1996
- Rigidity of planar tilingsInventiones Mathematicae, 1993
- Rigidity of planar tilingsInventiones Mathematicae, 1992
- On translating one polyomino to tile the planeDiscrete & Computational Geometry, 1991
- Three-dimensional analogs of the planar penrose tilings and quasicrystalsDiscrete Mathematics, 1989
- Undecidability and nonperiodicity for tilings of the planeInventiones Mathematicae, 1971