Undecidability of translational tiling of the 4-dimensional space with a set of 4 polyhypercubes
摘要
Recently, Greenfeld and Tao (2024) disproved the conjecture that translational tilings of a single tile can always be periodic. In another paper (Greenfeld and Tao (2025)), they also showed that if the dimension n is part of the input, the translational tiling for subsets of ℤn with one tile is undecidable. These two results are very strong pieces of evidence for the conjecture that translational tiling of ℤn with a monotile is undecidable for some fixed n. In this paper, we show 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 the 3-dimensional space to the 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.