{"id":"43b6a243-6cfe-4d3f-be41-d31b76e7a20e","arxiv_id":"2508.11725","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The translational tiling problem for Z^3 is undecidable even for a set of two connected polycubes.","lead":"This paper proves that it is undecidable whether two connected polycubes can tile three-dimensional integer space by translations, improving the smallest known tile count for undecidable 3D tiling. It introduces a technique for converting disconnected tiles into connected ones and reduces the problem to a variant of Wang's domino problem.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Central reduction depends on unproved forcing lemmas: Lemma 2.4 and Lemma 4.4 assert that added bumps/dents lock all tiles onto a prescribed lattice/period, but no proof is supplied; if misaligned tilings exist, the equivalence with cyclic triomino problems breaks.","rationale":"The reader's weakest-assumption analysis identifies exactly the same load-bearing gap: Lemma 2.4 and Lemma 4.4 are asserted without proof, and the entire reduction from translational tiling to the cyclic triomino problem depends on them. My independent reading of the paper confirms that these are not minor omissions: there is no geometric argument showing that the added bumps and dents prevent off-lattice placements or non-multiple-of-6 vertical shifts. The lemmas may well be true, and the paper's overall strategy is plausible, but as written the proof is incomplete. I therefore do not change the reader's CONDITIONAL verdict; the concern reinforces it rather than overturning it. A finite computational check on a small instance is the most direct way to settle whether the asserted forcing actually holds.","tokens_in":13455,"tokens_out":5429,"duration_ms":59881,"concrete_test":"Test Lemma 4.4 on a small explicit instance, e.g. n=5 with a cyclic triomino set for which m=1, so the 3-brick's coordinates are fully specified. Encode the tiling of a bounded box containing one 3-brick and a second 3-brick at z-offsets 0,1,2,3 (relative to the first), with the 3-filler allowed in the complement, into a SAT/ILP solver. If any placement with a z-offset not divisible by 6 admits a complete tiling of the box, Lemma 4.4 is false. If the solver reports UNSAT for all non-multiple offsets, enlarge the box by one period in each direction and repeat; sustained UNSAT would support the forcing claim, while SAT would disprove it.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The theorem's correctness hinges on two placement-forcing claims that are asserted rather than demonstrated. Lemma 2.4 states: 'If Sl tiles Z^3, the dents and bumps on Q'_1 force all copies of Q'_1 to lie on a lattice of side length 3m+6.' This is the only argument preventing copies of Sl from interlocking at offsets outside (3m+6)Z^3; without it, Theorem 2.5's simulation of disconnected polycubes by connected polycubes collapses. Lemma 4.4 similarly asserts, in two sentences, that the added bumps/dents on the 3-brick force an infinite vertical array with period 6n, aligned array edges, and z-coordinate differences that are multiples of 6. These geometric constraints are exactly what converts a tiling of Z^3 by the 3-filler and 3-brick into a solution of the cyclic triomino problem. No coordinates are analyzed, no case analysis is given, and no invariant is established ruling out tilings in which a bump of one brick sits against a dent-free face of another brick or inside a filler gap. Because both lemmas are load-bearing and unproved, the central claim is conditional on their validity.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":13826,"tokens_out":10656,"duration_ms":122017,"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":[{"comment":"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":"Section 2.2, Lemma 2.4"},{"comment":"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":"Section 4.2, Lemma 4.4"},{"comment":"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.","section":"Section 4.2, after Lemma 4.3 / before Lemma 4.4"}],"minor_comments":[{"comment":"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.","section":"Section 3.1, paragraph after Figure 7"},{"comment":"The caption says 'for m = 4', while the preceding text says the case m = 3 is shown. The caption and text should agree.","section":"Figure 3 caption"},{"comment":"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.","section":"Section 5, proof of Lemma 5.2"},{"comment":"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.","section":"General notation"}],"recommendation":"major_revision","confidential_remarks":"The paper presents a promising approach to a significant open problem. The main structural reduction is well motivated, and the cyclic triomino encoding is original and carefully built. However, the two placement-forcing lemmas (2.4 and 4.4) are central and currently unproved; they cannot be treated as routine geometric checks. If the author can supply complete proofs of these lemmas (or replace them with alternative forcing mechanisms), the paper would be a strong contribution. I recommend major revision rather than rejection, as the issues appear potentially fixable within the manuscript's framework. I also note the false statement about the cyclic domino problem and the scaling inconsistency; these should be corrected."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This paper claims undecidability of translational tiling with two polycubes in Z^3, which would close the (n,k)=(3,2) parameter and is a genuinely new result. The high-level structure is clever: introduce a \"cyclic triomino problem,\" prove it undecidable by encoding the domino problem, then encode that with two disconnected tiles, then simulate disconnected tiles with connected ones using the Sl gadget. The simulation technique in Section 2 is the real contribution and looks reusable.\n\nBut the proof as written has two load-bearing gaps, and they are exactly where the reader and stress-test flags them. Lemma 2.4 asserts that bumps and dents on Q'_1 force all copies of Sl onto a (3m+6)-lattice. The proof is one sentence: \"the dents and bumps ... force...\" No coordinates, no case analysis, no invariant. That is not a routine check, because it is what prevents misaligned interlockings that would break the equivalence between Sl-tilings and tilings of the original disconnected set. Lemma 4.4 does the same for the 3-brick: two sentences asserting that vertical arrays, edge alignment, and z-differences are forced. These are the exact constraints that turn a tiling of Z^3 by two tiles into a solution of the cyclic triomino problem. If a tiling exists where a bump meets a dent-free face or a filler gap, the reduction collapses. The paper does not supply the missing argument.\n\nThe rest of the paper is in better shape. The cyclic triomino undecidability proof is detailed, and the block/tower verification has a clear combinatorial check. The construction of the brick and filler is concrete, with a plausible mapping from solutions to tilings and back. But because both directions rely on Lemma 4.4, the central claim is conditional.\n\nThis is not a case where the gaps look cosmetic or easily filled by a reader - they are the heart of the rigidity argument. That said, the approach may be right, and the paper deserves a serious referee who can either fill the gaps or find a counterexample to the forcing claims. I would want the author to expand these lemmas with actual coordinate arguments before believing the theorem.\n\nWho is this for? Researchers in combinatorial tiling and decidability. It is a useful read for anyone thinking about how to build connected tiles from disconnected ones.\n\nRecommendation: send to peer review, but with a strong request to prove Lemma 2.4 and Lemma 4.4 in detail. As it stands, I would not cite it as a proof.","headline":"Plausible and important if true, but the two forcing lemmas are genuinely unproved and the result stands or falls on them.","tokens_in":14266,"tokens_out":1941,"would_cite":false,"duration_ms":22426,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["52C22","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that no algorithm can decide whether a given pair of connected polycubes tiles $\\mathbb{Z}^3$ by translation.","keywords":["translational tiling","polycubes","undecidability","cyclic triomino problem","connected tiles","simulation of disconnected tiles","domino problem","Z^3 tiling"],"falsifier":"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.","tokens_in":13383,"feed_emoji":"🧩","tokens_out":9014,"duration_ms":96283,"temperature":0.7,"pith_summary":"This paper proves the undecidability of a boundary case of translational tiling: no algorithm can decide whether a set of two connected polycubes tiles $\\mathbb{Z}^3$ by translation. The proof works by passing through a new intermediate problem, the cyclic triomino problem, and showing that it is undecidable by encoding an arbitrary domino problem without using a fixed coordinate system. It then builds two polycubes, the 3-brick and the 3-filler, that tile space exactly when a given cyclic triomino problem is solvable. A separate simulation construction converts any set of $k$ disconnected polycubes into $k$ connected polycubes with the same tiling behavior, which is what upgrades the two-tile construction to connected tiles.","feed_headline":"Tiling 3D space with two polycubes is undecidable","feed_subtitle":"New reduction encodes an undecidable domino problem in just two connected 3D pieces.","key_machinery":"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","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines the domino problem and proves it undecidable; Theorem 3.1 reduces the cyclic triomino problem to this result.","marker":"[3]"},{"why":"Establishes the undecidability of Wang's domino problem, the underlying undecidability source cited for the domino problem.","marker":"[1]"},{"why":"Introduces Wang tiles and the domino problem, the starting point of the undecidability chain described in the introduction.","marker":"[7]"}],"fun_headline_variants":["Two polycubes make 3D tiling undecidable","Undecidable tiling with just two polycubes","Tiling 3D with two polycubes: impossible to decide","Even two polycubes cannot be tiling-decided","Two polycubes: undecidable translational tiling"],"cache_read_input_tokens":2816,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Two polycubes make 3D tiling undecidable","Undecidable tiling with just two polycubes","Tiling 3D with two polycubes: impossible to decide","Even two polycubes cannot be tiling-decided","Two polycubes: undecidable translational tiling"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000551,"raw_usage":{"total_tokens":2420,"prompt_tokens":652,"completion_tokens":1768,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":396,"completion_tokens_details":{"reasoning_tokens":1682}},"tokens_in":396,"tokens_out":1768,"duration_ms":13550,"temperature":1.0,"reasoning_tokens":1682,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T20:03:16.901422+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Undecidability of translational monotilings","cited_arxiv_id":"2309.09504","evidence_quote":"Defines the domino problem and proves it undecidable; Theorem 3.1 reduces the cyclic triomino problem to this result."},{"cited_title":"Berger, The undecidability of the domino problem, Memoirs of the American Mathematical Society �� (1966), 1–72","cited_arxiv_id":null,"evidence_quote":"Establishes the undecidability of Wang's domino problem, the underlying undecidability source cited for the domino problem."},{"cited_title":"Wang, Proving theorems by pattern recognition-II , Bell System Technical Journal �� (1961), no","cited_arxiv_id":null,"evidence_quote":"Introduces Wang tiles and the domino problem, the starting point of the undecidability chain described in the introduction."}],"review_version":1}