Pith. sign in

REVIEW 3 major objections 5 minor 18 references

Undecidability of Translational Tiling of the Plane with Four Tiles

T0 review · 3 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Translational tiling of the plane with a set of four polyominoes is undecidable, by a reduction from Wang's domino problem.

desk verdict The stress-test's arithmetic objection is a misread—the paper's 'distance' is the gap between encoding blocks, not slot starts, and it checks out; the real weakness is the sketchy case analysis in Section 4. read the letter →

arxiv 2506.19295 v1 pith:USMWBTMQ submitted 2025-06-24 math.CO cs.CGmath.MG

Chao Yang , Zhujun Zhang This is my paper · ORCID
classification math.COcs.CGmath.MG MSC 52C2268Q17
keywords translationaltilingpolyominoundecidabilityWangtilesdominoproblemfixednumberofdisconnected
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves that no algorithm can decide, for an arbitrary set of four polyominoes, whether translated copies of the set cover the plane. The proof works by taking any finite set of Wang tiles and building four specifically shaped polyominoes that tile the plane exactly when the Wang tiles do. Because the Wang domino problem is known to be undecidable, the four-tile translational tiling problem inherits that undecidability. The result sharpens the smallest known tile count for undecidability from five to four.

What carries the argument

The machinery is a reduction built from four named pieces: a tiny filler (a plus-shaped polyomino that cannot tile alone and fills residual holes), a linker (a fixed building block whose single set of dents and bumps joins the color-matching system), a locator (a long two-row assembly of labeled building blocks that forces a rigid lattice pattern), and an encoder (a one-row assembly holding triplicated encodings of the Wang tiles). Lemma 2.1 gives the local rule: two building blocks stack without overlap exactly when the bump sets on facing sides are contained in the opposite dent sets, and the plus-shape holes are then filled by the tiny filler. The locators lock into a lattice, the encoders can shift horizontally, and the triple copies plus power-of-two slot indices guarantee that a shifted encoder never aligns two encoding regions in a way that creates an overlap.

What would settle it

The specific place to look is the Section 4 claim that every tiling contains the rigid locator lattice: exhibit a single tiling of the four tiles in which the locators are not arranged in that lattice, and the equivalence with Wang tilings is disproved. Conversely, a computer search on a non-tileable Wang set that finds no tiling of the polyomino set on arbitrarily large finite regions supports the claim.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is Theorem 1.3: translational tiling of the plane with a set of four polyominoes is undecidable. The four tiles are a tiny filler, a linker, a locator, and an encoder; for every finite Wang tile set these pieces are assembled so that a plane tiling exists if and only if the Wang set has a tiling. The reduction uses plus-shape dents and bumps to encode edge colors, a single linker that joins the two matching systems instead of the two linkers used in earlier proofs, and an encoder that stores three copies of each simulated Wang tile so that local flexibility in shifting encoders can always avoid overlaps. Undecidability then transfers from Wang's domino problem.

Load-bearing premise

The proof assumes that the local matching rules of Lemma 2.1 force every tiling to arrange the locators in the rigid infinite lattice described in Section 4 and expose exactly one simulated Wang tile per encoder; if some exotic arrangement bypassed that lattice, the claimed equivalence would collapse.

Editorial extensions

If this is right

  • The translational tiling problem with a fixed number of tiles is undecidable for four tiles, not just for five.
  • The four constructed tiles are allowed to be disconnected; for the same construction, requiring connected tiles would need a separate argument.
  • The reduction transfers Wang undecidability directly, so the four-tile problem inherits the absence of any general decision algorithm.
  • The techniques of unequal-distance placement of encoding portions and threefold duplication of each simulated Wang tile are the reason the two linkers of earlier reductions could be merged into one.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The single-linker trick is a general template: any reduction that currently needs two linkers could in principle fuse them if the encoder stores redundant copies, so the same idea may lower tile counts in other undecidability constructions, for instance in higher dimensions.
  • The triple-copy redundancy trades tile count for tile size: the locator and encoder grow with the number of simulated Wang tiles, so the undecidability proof relies on unboundedly large tiles.
  • The pigeonhole placement argument suggests that a construction with only two copies of each Wang tile might fail exactly at the overlap-avoidance step, so three copies may be the minimal redundancy for this framework.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper proves that the translational tiling problem for the plane is undecidable when the input is a set of exactly four (possibly disconnected) polyominoes. The proof follows the reduction framework initiated by Ollinger: from an arbitrary finite Wang tile set with n tiles and m colors, the authors construct four polyominoes (a tiny filler, a linker, a locator, and an encoder) whose translational tilings are in bijective correspondence with valid Wang tilings of the same Wang tile set. The claimed innovations are the use of a single linker instead of two, and a three-copy redundancy inside the encoder that permits a pigeonhole argument to resolve local overlap conflicts. The main theorem is stated as Theorem 1.3. The construction is genuinely parameter-dependent on the Wang tile set, and the reduction is argued in both directions. However, the proof of the key rigidity and compatibility claims in Section 4 is presented as a sequence of assertions rather than a complete case analysis, and the size arithmetic in Section 3 uses a distance convention that is not explicitly defined.

Significance. If fully proved, this would improve the previous best bound of five polyominoes (Kim) to four, continuing a well-established line of work from Ollinger's eleven tiles, through Yang and Zhang's ten, nine, eight, and seven tiles. The proposed single-linker construction is a plausible and interesting mechanism for reducing the tile count, and the three-copy redundancy idea is a notable technical device. The significance is moderated by two factors: the tiles are allowed to be disconnected, which is a relaxation of the usual notion of polyomino in much of the literature, and the proof as written is a convincing sketch rather than a fully rigorous derivation. The paper does not rely on fitted parameters or circular reasoning, and the reduction directions are standard; the main question is whether the asserted combinatorial rigidity and compatibility arguments can be made fully rigorous within the manuscript's framework.

major comments (3)
  1. [§4, "The locators form a rigid lattice pattern"] This is the load-bearing step of the proof, but it is only asserted. The paragraph starting "Put a locator any where in the plane" concludes that the locators form an infinite rigid lattice after applying the same argument repeatedly. A rigorous proof must show that every tiling contains such a lattice: no encoder can avoid exposing a marker, no two locators can be displaced or rotated relative to one another, and the propagation from one locator to all of Z^2 is forced. Without this exhaustive case analysis, the equivalence 'every polyomino tiling simulates a Wang tiling' is not established.
  2. [§4, "The locators and the encoders can be compatible"] The compatibility analysis is also a sketch. The text claims that a newly added encoder has three possible locations and that the pigeonhole principle guarantees a location avoiding total alignment with the two encoders below it, but the set of admissible horizontal shifts is not formally defined, and the two forbidden alignments are not shown to be the only obstructions. Similarly, the final bullet asserts that "all the remaining gaps can be filled by the linkers and the tiny fillers" without giving the filling algorithm or proving that no unfillable hole ever appears. These are essential for the converse direction 'any Wang tiling yields a polyomino tiling' and for the forward direction's completeness.
  3. [§3, encoder size calculations] The distance convention is ambiguous and this ambiguity affects the central invariant. A direct calculation of the distance between the starts of corresponding slots gives 2^{3n}(t+2)-t-1, which is L+t, not L. The padding formula in the paragraph 'Third, we compute the length of the padding segment...' is consistent with measuring the distance from the end of the left encoding blocks to the start of the right encoding blocks, since A+P-t = L. The text should state this convention explicitly; otherwise the assertion in §4 that the two exposed portions of an encoder are exactly the left and right encoding blocks of the same simulated Wang tile appears to be contradicted by the paper's own arithmetic.
minor comments (5)
  1. [Introduction and Section 2] The definition of polyomino as possibly disconnected should be flagged at the point where Problem 1.2 is stated. If the standard problem in the literature assumes connected polyominoes, the comparison with the previous five-tile result should explicitly state that the new result is for the disconnected variant.
  2. [Section 2] The proof of 'The tiny filler alone cannot tile the plane' can be made immediate with a checkerboard coloring argument: the plus-shape covers one square of one parity and four of the other, so translations of it cannot tile the parity-balanced plane.
  3. [Throughout] Several exponentiation symbols are missing or malformed in the text, e.g., '23n−1' should be '2^{3n-1}', and '23n(t+2)' should be '2^{3n}(t+2)'. Please correct all such typographical issues.
  4. [Figure 8] The caption contains a typo: '2043 builiding blocks' should be '2043 building blocks'.
  5. [Section 5] The remark about improving (4,3) to (3,3) in a forthcoming paper is interesting, but it should be clearly labeled as an announcement, not a claim proved in this manuscript.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: standard many-one reduction from Wang’s domino problem with construction parameters set by design, not fitted.

full rationale

The paper is a classic many-one reduction: given an arbitrary instance W of Wang’s domino problem, it constructs four polyominoes (tiny filler, linker, locator, encoder) and proves in Section 4 that the four-tile set tiles the plane if and only if W is tileable. No fitted parameters are extracted from data; the locator and encoder sizes are fixed by explicit formulas in Section 3 to implement the intended simulation, and the “distance equals locator length” invariant is a design constraint built into the construction, not an input assumed from the theorem being proved. The cited works by the same authors [13]–[16] are contextual history of earlier bounds, and the citation to [8] is for a particular filler shape; neither carries the logical weight of Theorem 1.3. The genuinely load-bearing external inputs are Berger’s undecidability theorem [3] and the Beauquier–Nivat characterization [2], which are independent known results. The equivalence is argued in both directions, and the local-flexibility/pigeonhole argument is a proof obligation rather than a circular reuse of the conclusion. Even if the size arithmetic in Section 3 were wrong, that would be a correctness issue, not a circular dependency.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The construction does not fit any empirical constants. The sizes such as 2^{3n-1}(t+2) and 23n(t+2)-2t-1 are functions of the input Wang tile set parameters (n,m,t), not free parameters chosen to make the proof work. The four polyomino shapes are ordinary mathematical objects, not independently postulated entities. The main load-bearing assumption is that label-based local matching fully determines global tiling behavior.

assumptions (4)
  • standard math Berger's theorem: Wang's domino problem is undecidable (Theorem 1.1).
    The reduction in Section 4 uses this classic result as the source of undecidability.
  • standard math Beauquier-Nivat pseudo-hexagon characterization implies the plus-shaped tiny filler cannot tile the plane by translations alone.
    Used in Section 4 to force locators into every tiling; the specific application is asserted as 'obvious' rather than proven in detail.
  • domain assumption The local label matching rules in Lemma 2.1 suffice to prevent overlap and to guarantee global compatibility of building blocks.
    The proof assumes that checking adjacent building blocks by labels is enough to control the whole tiling; this is used throughout Section 4.
  • domain assumption Polyominoes may be disconnected, a deliberate domain choice stated in Section 1.
    The main theorem is proved only for disconnected tiles; the connected four-tile case remains open and is explicitly listed as an open question.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Undecidability of Translational Tiling of the Plane with Four Tiles." pith.science (2026). https://pith.science/paper/USMWBTMQ

@misc{pith2026250619295,
  author       = {Pith},
  title        = {Pith review of: Undecidability of Translational Tiling of the Plane with Four Tiles},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/USMWBTMQ}},
  note         = {Machine review of arXiv:2506.19295}
}
abstract

The translational tiling problem, dated back to Wang's domino problem in the 1960s, is one of the most representative undecidable problems in the field of discrete geometry and combinatorics. Ollinger initiated the study of the undecidability of translational tiling with a fixed number of tiles in 2009, and proved that translational tiling of the plane with a set of $11$ polyominoes is undecidable. The number of polyominoes needed to obtain undecidability was reduced from $11$ to $7$ by Yang and Zhang, and then to $5$ by Kim. We show that translational tiling of the plane with a set of $4$ (disconnected) polyominoes is undecidable in this paper.

Figures

Figures reproduced from arXiv: 2506.19295 by the authors.

Figure 1
Figure 1. A set of 3 Wang tiles Note the size (i.e., number of tiles) of the set of Wang tiles can be arbitrarily large in Wang’s domino problem. If the size of the set of Wang tiles is fixed, then Wang’s domino problem is decidable, as there are only a finite number of instances. 2020 Mathematics Subject Classification. Primary 52C22; Secondary 68Q17. Key words and phrases. tiling, translation, undecidability, polyomino. 1 a… view at source ↗
Figure 2
Figure 2. A rectangular polyomino of size 14 × 84. The basic shape of the dents or bumps is the plus-shape polyomino illustrated in [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. The tiny filler (plus-shape). As we have mentioned, the building blocks can be viewed as two rows of level-2 squares, with 12 level-2 squares on each row. We divide the building block into three segments: the left segment consists of 5 × 2 level-2 squares on the left, the right segment consists of 5 × 2 level-2 squares on the right, and the middle segment consists of 2 × 2 level-2 squares in the middle. The level-2 … view at source ↗
Figures from the paper (10 more)
Figure 4
Figure 4. Figure 4: The linker: a building block with label {A||C} on the north and {A||C} on the south (left), and its symbolic representa￾tion (right). For each level-2 square (of left or right segments) in the first row (resp. second row), a dent or a bump can be added to the north (re…
Figure 5
Figure 5. Figure 5: A building block with label {||C, M} on the south (left), and its symbolic representation (right). A C L M R R M L C A A C L M R R M L C A F N N F {||} {||} [PITH_FULL_IMAGE:figures/full_fig_p005_5.png]
Figure 6
Figure 6. Figure 6: A blank building block with label {||} on the north and {||} on the south (left), and its symbolic representation (right). When the building blocks are put together to form bigger tiles, sometimes only one of the two sides (the north and south sides) is exposed as the …
Figure 7
Figure 7. Figure 7: A building block with label {C|F|A} on the north and {C|N|A} on the south (left), and its symbolic representation (right). With the notations for labeling the building blocks, we can state the following lemma on the conditions under which two building blocks can be pla…
Figure 8
Figure 8. Figure 8: The locator The locator is illustrated in [PITH_FULL_IMAGE:figures/full_fig_p007_8.png]
Figure 9
Figure 9. Figure 9: The two portions encoding a Wang tile and {C|F|A}{C|F|A}, respectively. The northwest and southwest edges of a Wang tile are encoded in the left portion, and the northeast and southeast sides are encoded in the right portion. Together, the two portions encode a complet…
Figure 10
Figure 10. Figure 10: The encoder With the portions for encoding the Wang tiles, it is now ready to define the encoder. The encoder that encodes the set of Wang tiles in [PITH_FULL_IMAGE:figures/full_fig_p008_10.png]
Figure 11
Figure 11. Figure 11: The rigid tiling pattern (not to scale) locators are the encoding building blocks of the same simulated Wang tile. This flexibility simulates the choice of a Wang tile in each place. • The locators and the encoders can be compatible. Still, we have to check the rigid …
Figure 12
Figure 12. Figure 12: Two adjacent encoders possibly overlap (not to scale). The reason that each simulated Wang tiles appear three times in the encoder is to avoid possible overlap (as illustrated in [PITH_FULL_IMAGE:figures/full_fig_p011_12.png]
Figure 13
Figure 13. Figure 13: Two adjacent encoders compatible with each other (not to scale). For two adjacent exposed sequence of encoding building blocks, say i and j in [PITH_FULL_IMAGE:figures/full_fig_p012_13.png]

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 13 canonical work pages

  1. [1]

    Ammann, B

    R. Ammann, B. Gr¨ unbaum, G. C. Shephard, Aperiodic tiles,Discrete & Computational Geometry,8(1992), 1-25

    work page 1992

  2. [2]

    Beauquier, M

    D. Beauquier, M. Nivat, On translating one polyomino to tile the plane,Discrete & Compu- tational Geometry,6(1991), 575-592

    work page 1991

  3. [3]

    Berger, The undecidability of the domino problem,Memoirs of the American Mathemat- ical Society,66(1966), 1-72

    R. Berger, The undecidability of the domino problem,Memoirs of the American Mathemat- ical Society,66(1966), 1-72

    work page 1966

  4. [4]

    Bhattacharya, Periodicity and decidability of tilings ofZ 2.American Journal of Mathe- matics,142(2020), 255-266

    B. Bhattacharya, Periodicity and decidability of tilings ofZ 2.American Journal of Mathe- matics,142(2020), 255-266

    work page 2020

  5. [5]

    Greenfeld, T

    R. Greenfeld, T. Tao. The structure of translational tilings inZ d. Discrete Analysis. (2021:16). 1-28

    work page 2021

  6. [6]

    Greenfeld, T

    R. Greenfeld, T. Tao, A counterexample to the periodic tiling conjecture.Annals of Mathe- matics,200(1)(2024), 301-363

    work page 2024

  7. [7]

    Greenfeld, T

    R. Greenfeld, T. Tao, Undecidability of translational monotilings. to appear inJournal of the European Mathematical Society, arXiv:2309.09504 [math.CO]

    arXiv

  8. [8]

    Kim, Undecidability of tiling the plane with a set of 5 polyominoes, (2025), a manuscript

    Y. Kim, Undecidability of tiling the plane with a set of 5 polyominoes, (2025), a manuscript

    2025

Show all 18 references
  1. [9]

    Ollinger, Tiling the plane with a fixed number of polyominoes, In: A.H

    N. Ollinger, Tiling the plane with a fixed number of polyominoes, In: A.H. Dediu, A.M. Ionescu, C. Mart´ ın-Vide (eds), Language and Automata Theory and Applications (LATA 2009). Lecture Notes in Computer Science, vol 5457. Springer, Berlin, Heidelberg, 638-649

    2009

  2. [10]

    Bjorn Poonen, Undecidable problems: a sampler. In: J. Kennedy (ed.), Interpreting G¨ odel (2014), Cambridge Univ. Press, Cambridge. 211-241

    2014

  3. [11]

    Wang, Proving theorems by pattern recognition-II,Bell System Technical Journal, 40(1961) 1-41

    H. Wang, Proving theorems by pattern recognition-II,Bell System Technical Journal, 40(1961) 1-41

    1961

  4. [12]

    Winslow, An optimal algorithm for tiling the plane with a translated polyomino, In: K

    A. Winslow, An optimal algorithm for tiling the plane with a translated polyomino, In: K. El- bassioni, K. Makino (eds), Algorithms and Computation (2015), Springer, Berlin, Heidelberg, 3-13

    2015

  5. [13]

    Yang, Tiling the plane with a set of ten polyominoes,International Journal of Computa- tional Geometry & Applications,33(03n04)(2023), 55-64

    C. Yang, Tiling the plane with a set of ten polyominoes,International Journal of Computa- tional Geometry & Applications,33(03n04)(2023), 55-64

    2023

  6. [14]

    Yang, On the undecidability of tiling the plane with a set of 9 polyominoes (in Chinese), SCIENTIA SINICA Mathematica,55(6)(2025), 1113-1122

    C. Yang, On the undecidability of tiling the plane with a set of 9 polyominoes (in Chinese), SCIENTIA SINICA Mathematica,55(6)(2025), 1113-1122

    2025

  7. [15]

    C. Yang, Z. Zhang, Translational tiling with 8 polyominoes is undecidable,Discrete & Com- putational Geometry, (2024),https://doi.org/10.1007/s00454-024-00706-1

    2024 doi

  8. [16]

    C. Yang, Z. Zhang, Translational Aperiodic Sets of 7 Polyominoes. arXiv:2412.17382 [math.CO]

    arXiv

  9. [17]

    C. Yang, Z. Zhang, Undecidability of Translational Tiling with Three Tiles. arXiv:2412.10646 [math.CO]

    arXiv

  10. [18]

    C. Yang, Z. Zhang, Undecidability of Translational Tiling of the Plane with Orthogonally Convex Polyominoes. arXiv:2506.12726 [math.CO] 14 CHAO YANG AND ZHUJUN ZHANG School of Mathematics and Statistics, Guangdong University of Foreign Studies, Guangzhou, 510006, China Email a...

    arXiv

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.