Undecidability of Translational Tiling of the 4-dimensional Space with a Set of 4 Polyhypercubes

Abstract

Recently, Greenfeld and Tao disprove the conjecture that translational tilings of a single tile can always be periodic [Ann. Math. 200(2024), 301-363]. In another paper [to appear in J. Eur. Math. Soc.], they also show that if the dimension $n$ is part of the input, the translational tiling for subsets of ${\mathbb{Z}}^n$ with one tile is undecidable. These two results are very strong pieces of evidence for the conjecture that translational tiling of ${\mathbb{Z}}^n$ with a monotile is undecidable, for some fixed $n$. This paper shows that translational tiling of the $3$-dimensional space with a set of $5$ polycubes is undecidable. By introducing a technique that lifts a set of polycubes and its tiling from $3$-dimensional space to $4$-dimensional space, we manage to show that translational tiling of the $4$-dimensional space with a set of $4$ tiles is undecidable. This is a step towards the attempt to settle the conjecture of the undecidability of translational tiling of the $n$-dimensional space with a monotile, for some fixed $n$.

18 pages, 20 figures

References in corpus (3)

• A counterexample to the periodic tiling conjecture
• A proof of Ollinger's conjecture: undecidability of tiling the plane with a set of $8$ polyominoes
• Undecidability of Translational Tiling of the 3-dimensional Space with a Set of 6 Polycubes