REVIEW 3 major objections 4 minor
Undecidability of Translational Tiling with 2 Polycubes
T0 review · 3 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash
Pith's one-line read The paper proves that no algorithm can decide whether a given pair of connected polycubes tiles $\mathbb{Z}^3$ by translation.
desk verdict Plausible and important if true, but the two forcing lemmas are genuinely unproved and the result stands or falls on them. 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 load-bearing objects are the 3-brick, the 3-filler, and the simulation tile $S_l$. $S_l$ is assembled from a partition of a cube into $m$ connected pieces $Q_1,\dots,Q_m$ that are internally and externally adjacent, scaled by 3, with bumps and dents added to $Q_1$. Lemma 2.4 asserts that those bumps and dents force every copy of $S_l$ onto the lattice $(3m+6)\mathbb{Z}^3$, so $S_l$ behaves like a cube that can only be placed on that lattice. That rigidity is what lets arbitrary disconnected tilings be mimicked by connected tiles. In the main construction, one-dimensional blockers (on/off cells at residues mod 6) and interlaced towers encode forbidden triples; the 3-filler, which cannot t
What would settle it
Take a cyclic triomino set whose problem is solvable, build its 3-brick and 3-filler, and search for a translational tiling of $\mathbb{Z}^3$ in which two 3-bricks are offset by a vector outside $(9m+6)\mathbb{Z}\times 15\mathbb{Z}\times 18\mathbb{Z}$ or outside the vertical period $18n$; Lemma 4.4 says no such tiling exists.
Extended reading notes
Core claim
The central claim is Theorem 4.1: it is undecidable whether a set of two connected polycubes can tile $\mathbb{Z}^3$ by translation. For every cyclic triomino set $S$ with values in $\mathbb{Z}_n$ and $\gcd(n,6)=1$, the paper constructs two disconnected polycubes, the 3-filler and the 3-brick, such that they tile $\mathbb{Z}^3$ if and only if $S$ is solvable (Lemma 4.4). The 3-brick carries towers of blockers that forbid exactly the triples not allowed by $S$; the 3-filler can fill the leftover gaps only when the towers line up in the allowed congruence pattern. Since the cyclic triomino problem is undecidable (Theorem 3.1), the two-polycube tiling problem is undecidable. The simulation of S
Load-bearing premise
The proof relies on the claim that the bumps and dents on $S_l$ and on the 3-brick force every copy onto a fixed lattice, and this forcing is asserted rather than demonstrated in detail; if some tiling could place a copy shifted outside that lattice, the equivalence with the cyclic triomino problem would fail.
Editorial extensions
If this is right
- The parameter pair $(n,k)=(3,2)$ is settled for connected tiles: deciding whether two polycubes tile $\mathbb{Z}^3$ is impossible for any algorithm.
- Because the simulation theorem works for any number $k$ of disconnected polycubes in $\mathbb{Z}^3$, any future disconnected-tile undecidability result in three dimensions can be converted to connected tiles with no tile-count overhead.
- Theorem 5.1 extends the simulation to every dimension $n\ge3$, so connected and disconnected tiling sets of the same cardinality are equivalent in tiling power in all higher dimensions.
- The cyclic triomino problem provides a new undecidable constraint system whose cyclic symmetry avoids absolute coordinates, which is exactly the feature that makes a two-tile encoding possible.
Reading between the lines
- The same blocker-and-tower scheme could encode other finite-state constraint satisfaction problems by choosing different periods and offsets, potentially lowering the tile count in other dimensions or settings.
- Since the simulation preserves the number of tiles, an undecidable single disconnected tile in $\mathbb{Z}^n$ would immediately yield an undecidable connected monotiling, giving a concrete route toward the open $k=1$ case.
- The rigidity step, Lemma 2.4, is the part to scrutinize: if bumps and dents can be proven to force lattice alignment with a simpler shape, the simulation might transfer to two dimensions or to smaller tile sets.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proves that the translational tiling problem for Z^3 with two connected polycubes is undecidable. The proof proceeds in three stages: (i) a general technique (Section 2) that simulates any set of k disconnected polycubes by k connected polycubes, relying on a tiling S_l whose bumps and dents supposedly force all copies onto a lattice; (ii) an undecidable 'cyclic triomino problem' (Section 3) derived from Greenfeld–Tao's domino problem; and (iii) an encoding of cyclic triomino problems by two disconnected polycubes, the 3-brick and the 3-filler, which are then made connected via the Section 2 technique (Section 4). A higher-dimensional generalization of the simulation is given in Section 5.
Significance. The target result, undecidability for (n,k)=(3,2), would be a significant advance in the translational tiling decidability program, closing a parameter case that has remained open. The paper also introduces a genuinely new reduction idea: encoding the Greenfeld–Tao domino problem through a cyclic triomino variant, and a method for turning disconnected tiles into connected tiles with the same number of tiles. The explicit constructions of the 3-brick and 3-filler, and the reduction from the cyclice triomino problem, are valuable even if the forcing arguments need repair. However, two load-bearing geometric lemmas (Lemma 2.4 and Lemma 4.4) are asserted without proof. If those assertions fail, the equivalence between tiling and the triomino problem collapses. The result is therefore conditional on the validity of these forcing claims.
major comments (3)
- [Section 2.2, Lemma 2.4] Lemma 2.4 asserts without proof that the bumps and dents on Q'_1 force all copies of Q'_1 (and hence all copies of S_l) onto the lattice (3m+6)Z^3. This is the only mechanism preventing shifted or staggered arrangements of S_l in a tiling. The proof simply states the conclusion; it does not analyze how the three protrusions and three dents constrain the relative translations of adjacent tiles. The claim is not routine: a bump of one copy might fit into a dent of another copy shifted by a vector not in (3m+6)Z^3, or a bump could be covered by a different part of S_l in a non-lattice configuration. Since Theorem 2.5 and the final reduction to two connected polycubes both depend on this forced lattice, a rigorous proof is indispensable. Section 5 inherits the gap when it 'replicates the exact arguments'.
- [Section 4.2, Lemma 4.4] Lemma 4.4 is the linchpin of the main theorem, but its proof consists of two informal sentences. It asserts that the 3-bricks form an infinite vertical array with period 6n, that array edges are aligned, and that z-coordinates of adjacent bricks differ by multiples of 6. These are precisely the constraints that Lemma 4.3 needs to convert a tiling into a solution of the cyclic triomino problem. No case analysis is provided for the placement of bumps and dents relative to one another or to the 3-filler. The added bumps and dents are listed explicitly, so a verification could in principle be given, but none is. Until this forcing is proved, the equivalence between solvability of the cyclic triomino problem and tileability of Z^3 by the 3-brick and 3-filler is not established.
- [Section 4.2, after Lemma 4.3 / before Lemma 4.4] The scaling step introduces a possible inconsistency. Lemma 4.3 is stated for the unscaled brick, with the placement lattice {(3m+2)x, 5y, 6z} and period 6n in z. The 3-brick is then defined by scaling the brick by a factor of 3, so its dimensions become (9m+6) x 15 x 18n. Lemma 4.4 nonetheless states that the bumps force 'a period of 6n' in the vertical direction. A vertical array of 3-bricks with height 18n cannot have period 6n without overlaps unless bricks interlock in a way that is not described. The relation between the scaled lattice, the brick height, and the asserted period must be clarified.
minor comments (4)
- [Section 3.1, paragraph after Figure 7] The claim that the cyclic domino problem is solvable whenever R1 and R2 are nonempty is false. For example, with W=Z_n, R1={(0,1)+k(1,1)}, R2={(0,0)+k(1,1)}, no function T:Z^2 -> Z_n satisfies both the horizontal and vertical constraints. This remark is not used in the proof, but it should be corrected.
- [Figure 3 caption] The caption says 'for m = 4', while the preceding text says the case m = 3 is shown. The caption and text should agree.
- [Section 5, proof of Lemma 5.2] The induction proof of connectivity checks only the connection between the layers x_n=m and x_n=m+1. It is not fully clear why the points (i,i,0,...,0,m) and (i,i,0,...,0,m+1) lie in Q_{n,i}; this follows from the definition of f_n but should be stated explicitly. Minor.
- [General notation] The notation I_{a,b} is used without definition in Section 4.2. It is clear from context that I_{a,b}={x in Z: a <= x <= b}, but it should be defined.
Circularity Check
No significant circularity: the derivation reduces from the externally cited undecidable domino problem, and the polycube encoding is a genuine reduction rather than a renamed input.
full rationale
The paper's central chain is: prove the cyclic triomino problem undecidable by an explicit reduction from Greenfeld and Tao's domino problem (external citation), then encode any cyclic triomino instance into two polycubes whose tiling is equivalent to solvability of the triomino instance. No fitted parameters are introduced and later called predictions; no theorem is imported from the author's own prior work; there are effectively no self-citations at all. Lemma 3.5 shows S-cyclic triomino solvable iff R-domino solvable using concrete tuple comparisons and the parity lattice structure, so the undecidability claim has independent content. The polycube construction in Section 4 is also a standard many-one reduction: the brick and filler are defined from the forbidden triples, and Lemma 4.3 derives a solution T from a tiling, while the converse is verified directly. The only notable weaknesses are Lemma 2.4 and Lemma 4.4, which assert without proof that added bumps and dents force copies onto a prescribed lattice/array. Those are unproved geometric forcing claims, and if false they would invalidate the theorem, but they are not circular: the forcing conclusion is not identical by definition to the tiling assumption, and it is not obtained by citing the authors' own prior work. A missing proof is a correctness risk, not a circularity. Therefore the manuscript does not reduce its conclusion to its inputs by construction, and the circularity score is 0.
Assumptions & free parameters
assumptions (2)
- domain assumption Undecidability of the domino problem (Berger 1966; Greenfeld-Tao 2023)
- domain assumption Standard translational tiling model: tiles are finite subsets of Z^n and translations are by integer vectors
invented entities (3)
-
Cyclic triomino problem
independent evidence
-
S_l connector tile
independent evidence
-
3-brick and 3-filler
independent evidence
Cite this review
Pith. "Pith review of Undecidability of Translational Tiling with 2 Polycubes." pith.science (2026). https://pith.science/paper/REEJBERI
@misc{pith2026250811725,
author = {Pith},
title = {Pith review of: Undecidability of Translational Tiling with 2 Polycubes},
year = {2026},
howpublished = {\url{https://pith.science/paper/REEJBERI}},
note = {Machine review of arXiv:2508.11725}
}
abstract
In this paper, we prove that it is undecidable whether a set of two polycubes can tile $\mathbb{Z}^3$ by translation. The proof involves a new technique that allows us to simulate two disconnected polycubes with two connected polycubes. By expanding this technique to higher dimensions, we also prove that a set of disconnected tiles in $\mathbb{Z}^n$ can be simulated by the same number of connected tiles in $\mathbb{Z}^n$ for $n \geq 3$.
Reviewed August 5, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.