On the Undecidability of Tiling the $3$-dimensional Space with a Set of $3$ Polycubes
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911086700134400 |
|---|---|
| author | Yang, Chao Zhang, Zhujun |
| author_facet | Yang, Chao Zhang, Zhujun |
| contents | Translational tiling problems are among the most fundamental and representative undecidable problems in all fields of mathematics. Greenfeld and Tao obtained two remarkable results on the undecidability of translational tiling in recent years. One is the existence of an aperiodic monotile in a space of sufficiently large dimension. The other is the undecidability of translational tiling of periodic subsets of space with a single tile, provided that the dimension of the space is part of the input. These two results support the following conjecture: there is a fixed dimension $n$ such that translational tiling with a single tile is undecidable. One strategy towards solving this conjecture is to prove the undecidability of translational tiling of a fixed dimension space with a set of $k$ tiles, for a positive integer $k$ as small as possible. In this paper, it is shown that translational tiling the $3$-dimensional space with a set of $3$ polycubes is undecidable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_00192 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Undecidability of Tiling the $3$-dimensional Space with a Set of $3$ Polycubes Yang, Chao Zhang, Zhujun Combinatorics Computational Geometry Metric Geometry Translational tiling problems are among the most fundamental and representative undecidable problems in all fields of mathematics. Greenfeld and Tao obtained two remarkable results on the undecidability of translational tiling in recent years. One is the existence of an aperiodic monotile in a space of sufficiently large dimension. The other is the undecidability of translational tiling of periodic subsets of space with a single tile, provided that the dimension of the space is part of the input. These two results support the following conjecture: there is a fixed dimension $n$ such that translational tiling with a single tile is undecidable. One strategy towards solving this conjecture is to prove the undecidability of translational tiling of a fixed dimension space with a set of $k$ tiles, for a positive integer $k$ as small as possible. In this paper, it is shown that translational tiling the $3$-dimensional space with a set of $3$ polycubes is undecidable. |
| title | On the Undecidability of Tiling the $3$-dimensional Space with a Set of $3$ Polycubes |
| topic | Combinatorics Computational Geometry Metric Geometry |
| url | https://arxiv.org/abs/2508.00192 |