REVIEW 2 major objections 2 minor 8 references
Undecidability of Tiling the Plane with a Set of 5 Polyominoes
T0 review · 2 major / 2 minor · reviewed 2026-08-05 · deepseek-v4-flash
Pith's one-line read This paper proves that deciding whether a set of five polyominoes can tile the plane by translation is undecidable, via a new edge-labeling method that encodes arbitrary matching rules in a single polyomino.
desk verdict Claim is plausible, but the proof text is undecodable, so the paper as submitted cannot be evaluated. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is a labeling polyomino—a single piece whose boundary is shaped to encode edge types as physical labels. It works by making each exposed unit edge carry a label that can be made compatible or incompatible with any label on another piece, thereby realizing an arbitrary prescribed pairwise matching relation in geometry. The other four polyominoes then implement the tiles of a general edge-matching system, so every tiling of the encoded system corresponds to a tiling of the five-piece set, and vice versa.
What would settle it
Take a finite edge-matching rule system known to have no tiling, run the paper's construction to produce its five polyominoes, and search for a plane tiling—for example, a periodically repeating finite patch. Finding one would show the encoding admits spurious tilings; a correct decision procedure for five-polyomino translation tiling would also disprove the result.
Extended reading notes
Core claim
The central claim is that the translation-tiling problem for sets of exactly five polyominoes has no decision algorithm. The carrier of the argument is a new labeling method: a single specially built polyomino carries edge labels that force any two adjacent tiles to agree with a prescribed matching relation chosen in advance. This lets the author encode an arbitrary finite set of edge-matching rules into a set of five polyominoes, and a plane tiling of the polyomino set exists exactly when the encoded edge-matching system has a tiling. Since the latter problem is undecidable, so is the former.
Load-bearing premise
The load-bearing premise is that the labeling polyomino's geometry forces exactly the intended compatibility relation and never permits an unintended match that could create a tiling when the encoded edge-matching system has none.
Editorial extensions
If this is right
- The translation-tiling problem for five polyominoes is undecidable: no general algorithm can always report whether a given such set covers the plane.
- The result gives an explicit five-piece construction that simulates arbitrary finite edge-matching rules, so the undecidability is obtained constructively, not by a counting argument.
- No finite local condition computed from the pieces can characterize translation tileability of polyomino sets, because such a condition would yield a decision procedure.
- The undecidability holds even when rotations and reflections are disallowed, since the tiling is by translation only.
Reading between the lines
- Beyond the paper: because the labeling method stores arbitrary compatibility data on one piece, the same trick may lower the undecidability threshold in variants where rotations or reflections are allowed, or where the pieces must form a connected tile set.
- Beyond the paper: if the dedicated labeling polyomino cannot be merged into the other four without losing arbitrary compatibility, then five is the natural limit of this method; testing whether a four-piece analogue exists would settle whether the bound can be improved.
- Beyond the paper: the construction suggests a general dictionary between finite edge-matching constraint systems and constant-size polyomino sets, so other undecidable constraint problems could be translated into tiling questions with the same five-piece format.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper's abstract claims a proof that it is undecidable whether a set of five polyominoes can tile the plane by translation. The proposed method is a new edge-labeling scheme in which one of the five polyominoes is dedicated to enforcing arbitrary pairwise edge compatibilities, enabling a reduction from the Wang tiling problem. The submitted full text, however, is not readable as a mathematical manuscript: from the opening section onward it consists of replacement characters, with only fragments of headings and isolated formulas legible. No definitions, lemmas, or proof of the reduction or of the soundness of the encoding are accessible. The central claim is therefore unsupported by the artifact as received.
Significance. If the claimed result holds, it would be a substantive addition to the study of undecidable tiling problems, improving knowledge of the smallest size of a set of polyominoes for which the translational tiling decision problem is undecidable. The proposed 'labeling polyomino' idea could be of independent interest if it is made precise and proved correct. But the present artifact does not allow verification of the result, of the novelty relative to prior bounds, or of the correctness of the construction. The significance is conditional and cannot be assessed from the submitted text.
major comments (2)
- [Full text] The body of the manuscript is an undecodable byte sequence of replacement characters. There is no legible definition of the labeling polyomino, no statement of the main theorem with proof, no lemma that the encoding is sound and complete, and no demonstration that every tiling of the five-piece set projects to a valid Wang tiling. The stress-test concern lands: the one load-bearing gadget, the dedicated labeling polyomino, cannot be checked. This is not a claim that the result is false; it is a statement that the submitted manuscript does not permit refereeing.
- [Abstract] The abstract's key assertion that 'dedicating 1 polyomino to the labeling process' can realize arbitrary pairwise edge compatibility is not accompanied in any visible portion of the paper by a formal definition of edges, labels, or matching rules, nor by a statement of the exactness of the encoding. A rigorous treatment would need to prove both that every valid Wang tiling induces a tiling by the five polyominoes and that every tiling by the five polyominoes yields a valid Wang tiling (excluding spurious tilings). None of this is present in the readable fragments.
minor comments (2)
- [General] Only the title, abstract, article number, and date are legible; the reference list and all section numbering are lost. It is therefore impossible to check the paper's relation to earlier undecidability results for polyominoes or to compare with prior lower bounds.
- [Mathematical notation] The readable fragments of formulas are garbled and incomplete. Even if the encoding corruption were fixed, the paper would benefit from a clear formal statement of the theorem and a numbered lemma for the labeling construction.
Circularity Check
No significant circularity: the argument is a standard reduction from the undecidable Wang tiling problem, with no claim reducing to its own input or to self-citation.
full rationale
The paper's central claim is that the plane-tiling problem for sets of five polyominoes is undecidable. The abstract describes a reduction-style proof: it uses a new method of labeling polyomino edges so that arbitrary pairwise edge compatibilities can be enforced, and it dedicates one polyomino to the labeling process. This is a constructive encoding argument, not a circular derivation. The undecidability source is the classical Wang tiling problem, an external and standard undecidable problem, so the result is not obtained by assuming the conclusion. There is no fitted parameter that is later renamed as a prediction: the labeling polyomino is a new combinatorial gadget, not a quantity fitted to data. There is no visible load-bearing self-citation or imported uniqueness theorem; the abstract does not cite the authors' prior work as the justification for the construction. Even though the submitted full text is largely unreadable due to character corruption, that is a verifiability and correctness concern, not a circularity concern. Under the hard rules, an unreadable proof is not itself evidence of circularity, and no specific equation or construction in the readable portions reduces to its own input. The claimed derivation chain therefore does not exhibit self-definition, fitted-input-called-prediction, self-citation loading, ansatz smuggling, or renaming of a known result. Accordingly, the appropriate circularity score is 0.
Assumptions & free parameters
assumptions (2)
- standard math The Wang tiling problem is undecidable.
- ad hoc to paper The dedicated labeling polyomino implements arbitrary pairwise edge compatibility without introducing spurious tilings.
invented entities (1)
-
dedicated labeling polyomino
Cite this review
Pith. "Pith review of Undecidability of Tiling the Plane with a Set of 5 Polyominoes." pith.science (2026). https://pith.science/paper/2YPQHIDD
@misc{pith2026250810067,
author = {Pith},
title = {Pith review of: Undecidability of Tiling the Plane with a Set of 5 Polyominoes},
year = {2026},
howpublished = {\url{https://pith.science/paper/2YPQHIDD}},
note = {Machine review of arXiv:2508.10067}
}
read the original abstract
In this paper, we give a proof that it is undecidable whether a set of five polyominoes can tile the plane by translation. The proof involves a new method of labeling the edges of polyominoes, making it possible to assign whether two edges can match for any set of two edges chosen. This is achieved by dedicating 1 polyomino to the labeling process.
Reference graph
Works this paper leans on
-
[1]
R. Berger, The undecidability of the domino problem , Memoirs of the American Mathematical Society 66 (1966), 1--72
work page 1966
-
[2]
E. D. Demaine and S. Langerman, Tiling with Three Polygons is Undecidable , arXiv: 2409.11582 [cs.CG] (2024)
work page Pith review arXiv 2024
-
[3]
S. W. Golomb, Tiling with a set of polyominoes , Journal of Combinatorial Theory 9 (1970), 60--71
work page 1970
-
[4]
N. Ollinger, Tiling the Plane with a Fixed Number of Polyominoes , Language and Automata Theory and Applications 5457 (2009), 638--647
work page 2009
-
[5]
Wang, Proving theorems by pattern recognition-II , Bell System Technical Journal 40 (1961), no
H. Wang, Proving theorems by pattern recognition-II , Bell System Technical Journal 40 (1961), no. 1, 1--41
work page 1961
-
[6]
H.A.G. Wijshoff, J. van Leeuwen, Arbitrary versus periodic storage schemes and tessellations of the plane using one type of polyomino , Information and Control 62 (1984), no. 1, 1--25
work page 1984
-
[7]
C. Yang and Z. Zhang, Translational Tiling with 8 Polyominoes is Undecidable , Discrete Comput. Geom. (2024), 1--24
work page 2024
-
[8]
Translational Aperiodic Sets of 7 Polyominoes
C. Yang and Z. Zhang, Translational Aperiodic Sets of 7 Polyominoes , arXiv: 2412.17382 [math.CO] (2024)
work page Pith review arXiv 2024
Reviewed August 5, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.