Pith. sign in

REVIEW 3 cited by

Undecidability of translational monotilings

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2309.09504 v2 pith:JW6I4HGW submitted 2023-09-18 math.CO math.LO

classification math.COmath.LO
keywords translationalmathbbmonotilingsundecidabilitydecidabilityrecentlyspacestilings
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

In the 60's, Berger famously showed that translational tilings of $\mathbb{Z}^2$ with multiple tiles are algorithmically undecidable. Recently, Bhattacharya proved the decidability of translational monotilings (tilings by translations of a single tile) in $\mathbb{Z}^2$. The decidability of translational monotilings in higher dimensions remained unsolved. In this paper, by combining our recently developed techniques with ideas introduced by Aanderaa and Lewis, we finally settle this problem, achieving the undecidability of translational monotilings of (periodic subsets of) virtually $\mathbb{Z}^2$ spaces, namely, spaces of the form $\mathbb{Z}^2\times G_0$, where $G_0$ is a finite Abelian group. This also implies the undecidability of translational monotilings in $\mathbb{Z}^d$, $d\geq 3$.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Undecidability of Translational Tiling with 2 Polycubes

    math.CO 2025-08 conditional novelty 8.0 of 10

    The translational tiling problem for Z^3 is undecidable even for a set of two connected polycubes.

  2. Undecidability of Translational Tiling of the Plane with Orthogonally Convex Polyominoes

    math.CO 2025-06 conditional novelty 6.0 of 10

    Translational tiling of the plane with a set of seven orthogonally convex polyominoes is undecidable.

  3. Undecidability of Translational Tiling with Three Tiles

    math.CO 2024-12 conditional novelty 6.0 of 10

    Deciding translational tiling of Z^4 by three connected polyhypercubes is undecidable, shown by reduction from Wang's domino problem.

Pith tools