Skip to content
DraconiticResearch
Search Sources API
194,164 studies31 sourcesUpdated 37 min ago
PreprintarXiv licencearXiv

Tiling 3D by Translates of a Single Polycube is Undecidable

  • Erik D. Demaine
  • Stefan Langerman
Open at sourcePDFDOICite

Abstract

We prove co-RE-completeness, and thus undecidability, of the following problem: given a single (connected) polycube, decide whether it tiles 3D Euclidean space by translations. We reduce from Wang tiling using the decorated two-prime Sudoku construction of Greenfeld and Tao and a cyclic encoding adapted from OpenAI's 3D aperiodic tile, and apply a reduction of Kim to make the prototile connected (via faces). Dimension three is optimal: translational monotiling is known to be decidable in ℤ2 and for a single (possibly disconnected) polyomino in ℝ2.

Related

  1. Polycubes and polycube ideals
    Ayesha Asloob Qureshi, Dharm Veer
    arXivPreprintCC BY-NC-ND 4.0Full textAlgebra & number theoryarXiv
  2. Normal and Lognormal Asymptotics for Lattice-Point Counts in Random Translates of High-Dimensional Balls
    Xin Hang Ji
    arXivPreprintarXiv licenceFull textAlgebra & number theoryProbabilityarXiv
  3. Covering finite fields by translates of multiplicative subgroups
    Juncheng Zhou, Hongfeng Wu
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv
  4. Union of Translates of a Convex Body
    Alec Shelley, Daniel Tartakovsky
    arXivPreprintarXiv licenceFull textGeometry & topologyarXiv
  5. Depth based on translates of a convex body: geometry, floating bodies, and empirical theory
    Ilya Molchanov, Stanislav Nagy
    arXivPreprintCC BY 4.0Full textGeometry & topologyStatisticsarXiv

Cite

BibTeXRIS
BibTeX
@misc{demaine2026tiling,
  title = {{Tiling 3D by Translates of a Single Polycube is Undecidable}},
  author = {Erik D. Demaine and Stefan Langerman},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.12392},
  eprint = {2610.12392},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.12392},
}
RIS
TY  - UNPB
TI  - Tiling 3D by Translates of a Single Polycube is Undecidable
AU  - Erik D. Demaine
AU  - Stefan Langerman
PY  - 2026
DA  - 2026/10/08
PB  - arXiv
DO  - 10.48550/arxiv.2610.12392
UR  - https://arxiv.org/abs/2610.12392
AB  - We prove co-RE-completeness, and thus undecidability, of the following problem: given a single (connected) polycube, decide whether it tiles 3D Euclidean space by translations. We reduce from Wang tiling using the decorated two-prime Sudoku construction of Greenfeld and Tao and a cyclic encoding adapted from OpenAI's 3D aperiodic tile, and apply a reduction of Kim to make the prototile connected (via faces). Dimension three is optimal: translational monotiling is known to be decidable in ℤ^2 and for a single (possibly disconnected) polyomino in ℝ^2.
ER  -