{"id":"530ef2f6-10d8-405d-a965-9a38c6275644","arxiv_id":"2412.10646","paper_version":1,"verdict":"CONDITIONAL","confidence":"LOW","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Deciding translational tiling of Z^4 by three connected polyhypercubes is undecidable, shown by reduction from Wang's domino problem.","lead":"This paper proves that no algorithm can always decide whether three connected four-dimensional tile shapes can translate to fill all of the four-dimensional grid. The result moves the undecidability frontier from four tiles down to three in dimension four, a step toward the open question of whether one tile can do the same.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The claimed 5-frame time shift does not make c(4) complementary to D(4); the 4D one-linker-for-two-jobs mechanism in §3.3 appears algebraically false.","rationale":"The 3D construction (Theorem 2) is a serious and plausible reduction; the reader's identification of Fact 2 as under-derived is fair. However, I found a more specific, checkable failure in the 4D lift. The entire saving of one tile in Theorem 1 rests on the sentence in §3.3 that a linker can match two D(4) blocks by being translated 5 frames. Because the 4D encoder uses C(4)/D(4) in place of the 3D u/d, and the linker uses c(4) in place of the two 3D linkers' U/D, the matching condition is that c(4) shifted by some integer τ is exactly the complement of D(4) inside the same 10-frame functional hypercube. The explicit sequences in §3.1 make this a finite algebraic condition, and no such τ exists. Frame 1 requires c(4) to be full, forcing τ to be negative enough, while frame 6 requires c(4) to be empty, and subsequent frames are incompatible. Thus the 'one linker for two jobs' mechanism is not delivered by the specified shapes. If this is correct, the if-and-only-if between tilings of the three 4D tiles and Wang tilings is not established. The reader's Fact 2 concern is real but secondary: even if Fact 2 holds, the 4D time-shift argument fails at this algebraic step. I recommend rejecting the current proof unless the check produces a shift I missed or the intended geometry differs from the functional-hypercube complement reading. The central claim may still be true, but this paper's proof as written lacks a key structural justification.","tokens_in":15185,"tokens_out":24321,"duration_ms":223039,"concrete_test":"Extract the ten-frame masks of c(4), C(4), and D(4) from §3.1 and test every integer shift τ ∈ {-20,...,20} whether B_i ∪ c(4)_{i-τ} = K and B_i ∩ c(4)_{i-τ} = ∅ for all i = 1,...,10, for B = C(4) and B = D(4), treating out-of-range c(4) frames as empty. Repeat the same check for the two-sided linker geometry with c(4) on both north and south. If no τ exists for B = D(4), the 'translated 5 frames' matching claim in §3.3 is refuted and the proof of Theorem 1 needs a different mechanism; if such a τ exists, my objection is discharged.","verdict_should_be":"REJECT","load_bearing_attack":"The load-bearing step in §3.3 is the assertion that a single linker with building block c(4) can match two D(4) blocks by being translated 5 frames in time. This is what saves the second linker and enables the three-tile reduction. But the shapes defined in §3.1 do not satisfy that assertion. Writing the ten-frame occupancy sequences as c(4) = (∅, S2, S3, S4, K, K, K, K, K, K) and D(4) = (∅, ∅, ∅, ∅, ∅, K, T4, T2∪T4, T2∪T3∪T4, ∅), the matching condition is that for some integer time shift τ, D(4)_i ∪ c(4)_{i-τ} = K and D(4)_i ∩ c(4)_{i-τ} = ∅ for every frame i = 1,...,10, treating out-of-range frames as empty. Frame 1 forces c(4)_{1-τ} = K, so 1-τ is a frame where c(4) is K, i.e., τ ∈ {-9,...,-4}. Frame 6 forces c(4)_{6-τ} = ∅, which among these τ requires 6-τ = 10, i.e., τ = -4; but then frame 2 has c(4)_{6}? More directly, enumerating the ten frame equations gives no integer τ: the only candidate that makes frames 6-9 full forces τ = -4, yet frame 2 then has D(4)_2 = ∅ and c(4)_6 = K? In fact, a direct check shows no τ makes every frame full. Hence the linker c(4) cannot match two D(4) blocks by a 5-frame shift, and the 'good side, one linker for two jobs' is not realized by the specified shapes. The if-and-only-if with Wang tilings in Theorem 1 therefore lacks its central 4D matching mechanism.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript claims two undecidability results: (Theorem 2) translational tiling of Z^3 with four connected polycubes is undecidable, and (Theorem 1) translational tiling of Z^4 with three connected polyhypercubes is undecidable. The proof reduces from Wang's domino problem: colors of Wang tiles are encoded by arrangements of building blocks, and an encoder tile, linker tile(s), and a filler tile are constructed so that tilings of the polycube set correspond exactly to valid Wang tilings. The 4D result lifts the 3D construction by interpreting the fourth dimension as time and replacing the two 3D linker types with one linker that can be shifted in time.","tokens_in":15584,"tokens_out":18988,"duration_ms":177020,"significance":"If the proofs are completed, Theorem 1 is a genuine advance in the fixed-parameter undecidability frontier: it improves the number of tiles from four to three in dimension four and provides further evidence for the conjecture that translational tiling by a monotile is undecidable in some fixed dimension. The reduction strategy is coherent and builds on the external undecidability of Wang's domino problem, so there is no circularity. The main caveat is that the manuscript's central claim rests on several rigidity assertions (Facts 1 and 2 and their 4D analogues) that are not proved in the text, and the algebraic claims about the time-shift matching need a precise derivation. At present the result is plausible but not established.","major_comments":[{"comment":"The claim that in any tiling the linker representative points form exactly the lattice {(10x,60y,20pz)} is load-bearing, because the encoders are placed only in the gaps left by this lattice. No proof of this rigidity statement is supplied; the preceding paragraph says the north-south linker main body is 'exactly 3 building blocks away', which would suggest 30y rather than 60y, and the discrepancy is not explained. Without a complete rigidity proof, the 'if and only if' with Wang tilings is not established.","section":"Section 2.2, Fact 2"},{"comment":"The claim that every tiling of the four-tile set must use the encoder (and hence the linker) is not proved. The text argues that if the encoder is used then the linker must be used, and if the filler is used then the encoder must be used, but it does not rule out tilings consisting only of linkers, or of linkers plus fillers, in which no color information is encoded. Such tilings would break the 'only if' direction of the reduction, since a non-tiling Wang instance could still produce a tilable polycube set.","section":"Section 2.3, first bullet"},{"comment":"The statement that linkers can match D(4) blocks by being translated 5 frames is not derived from the frame sequences in Section 3.1. With c(4) = (∅, T1∪T2∪T3∪T5, T1∪T3∪T5, T1∪T5, K, K, K, K, K, K) and D(4) = (∅,∅,∅,∅,∅, K, T4, T2∪T4, T2∪T3∪T4, ∅), a single c(4) shifted by 5 frames fills exactly frames 6–10 of the D(4) hypercube but leaves frames 1–5 empty, since D(4) is empty there and the shifted c(4) has no frame in range at those times. The paper does not explain how these empty frames are filled, for example by another copy of the linker in an adjacent time slice, nor how such copies avoid overlap. This 5-frame shift is the key mechanism that reduces the tile count from four to three, so it must be proved explicitly.","section":"Section 3.3, matching D(4) by a 5-frame shift"},{"comment":"The proofs that encoders are aligned in time and that every 10-frame slice is identical are presented in prose. The contradiction argument against a C(4)/D(4) mismatch relies on Figure 24 without a formal case analysis, and the claims that V(4)/v(4), W(4)/w(4), and E(4) force global time alignment and slice-periodicity are asserted rather than proved. These properties are essential: the equivalence with Wang tilings requires that every valid tiling decomposes into identical slices with the same simulated Wang tile, and any alternative time-shift configuration would break that correspondence.","section":"Section 3.3, time alignment and slice periodicity"},{"comment":"The 4D construction is presented as an application of the lifting technique from [23,24], both of which are listed as 'to appear', and the rigidity statement in 4D is described as a 'slightly more involved argument' than Fact 2 without being given. Since the central theorem depends on these unpublished methods, the paper is not self-contained. Please state and prove the required lifting lemma, or give a complete proof of the 4D rigidity and time-alignment claims directly.","section":"Sections 3.2 and 3.3, reliance on prior work"}],"minor_comments":[{"comment":"There are typographical errors such as 'Ch ina' in the author affiliation; the manuscript should be carefully proofread.","section":"Abstract and affiliations"},{"comment":"The vertical spacing is written '20pz' without a separating space, and the y-spacing of 60 in Fact 2 appears inconsistent with the description of linkers being '3 building blocks away' in the north-south direction; please clarify the intended spacing.","section":"Section 2.2, Fact 2"},{"comment":"The sets T_i are defined informally as successive outer-surface layers of a 10×10×10 cube. Please provide explicit coordinate definitions so that the frame sequences of c(4), C(4), and D(4) are unambiguous and machine-checkable.","section":"Section 3.1, definition of T_i"},{"comment":"The phrases 'easy to check' and 'for a similar reason' are used for connectedness, complementarity, and rigidity properties that feed directly into the main argument. These should be replaced by short lemmas with proofs or explicit references.","section":"General use of 'easy to check'"},{"comment":"Many figures are grayscale or low-contrast and label building blocks only by letters without coordinates. Adding coordinate axes and explicit layer indices would make the construction much easier to verify.","section":"Figures"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is an extension of the authors' own prior work [23,24], and the soundness of the present paper depends heavily on the rigidity lemmas that are only asserted here. If the companion preprints are available, they should be consulted when evaluating Fact 2 and the time-alignment claims. The main novelty appears to be the time-shift linker mechanism, and the referee report should be read with the understanding that a complete proof of that mechanism is necessary before the three-tile claim can be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper proves that translational tiling of Z^4 with three connected polyhypercubes is undecidable, and also gives the 3D result with four polycubes. Both are genuinely new; the cited literature has (4,4) and (3,≥5) from the same program, so this is a real step down in tile count. The construction is a reduction from Wang's domino problem, and the new devices—the multiconnected encoder, the prefix/suffix color encoding, and the selective lifting to 4D—are real additions.\n\nWhat I found sound: the overall reduction strategy is coherent, the encoding of Wang colors with redundant bits is clean, and the 3D proof gives a plausible rigidity story. The 4D proof relies on the lifting technique the authors developed earlier; the idea of using one linker for both C(4) and D(4) by sliding in time is clever and, I checked, actually works—provided you read it as the full stack of linkers shifting 5 frames, not a single c(4) block in isolation. The stress-test note made that exact mistake; it treated the c(4) block as if it had to fill the whole 10-frame window alone. In the tiling, linkers are stacked along time, so the 5-frame offset lets the previous linker's c(4) fill the first half of a D(4) block and the next linker's c(4) fill the second half. The algebra closes.\n\nThe real soft spot is rigor, not correctness. Fact 2—the claim that linker representative points form the lattice {(10x,60y,20pz)}—is load-bearing and is asserted with diagrams and \"easy to check\" rather than a full derivation. The 4D analogue (rigid lattice in space, flexible in time; encoders forced to be identical across slices) is argued in prose. These are the places a referee should push. The conclusion's \"two steps away\" from the monotile problem is also overoptimistic phrasing; the gap from three tiles to one is not measured in simple steps.\n\nOverall: the central theorem is plausible and likely correct, but the written proof needs the geometric forcing lemmas made precise. This is exactly the kind of paper that deserves a serious referee, with requests for full proofs of the rigidity facts. If those hold up, the result is a solid contribution to the undecidability frontier. I'd send it to review.","headline":"Genuinely new frontier result (three connected tiles in Z^4), with a sound reduction strategy; the main weakness is that the load-bearing rigidity lemmas are asserted rather than fully derived, so the paper deserves peer review with a request for complete proofs.","tokens_in":16172,"tokens_out":15189,"would_cite":true,"duration_ms":122114,"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":"Translational tiling of 4-dimensional space with three connected tiles is undecidable.","keywords":["translational tiling","undecidability","Wang domino problem","polyhypercubes","polycubes","aperiodic monotile conjecture","dimension 4 tiling"],"falsifier":"Look for a valid tiling of $\\mathbb{Z}^4$ by the three constructed tiles whose linker representative points are not all on the lattice $\\{(10x,60y,20pz)\\}$, or in which two time slices have different encoder arrangements. A targeted way to search is to tile a finite torus whose side lengths are multiples of the construction's periods; any solution that does not descend to a Wang tiling of the matching layer would falsify the rigidity step on which the reduction rests.","tokens_in":14951,"feed_emoji":"🧩","tokens_out":12702,"duration_ms":111859,"temperature":0.7,"pith_summary":"The paper argues that the translational tiling decision problem is undecidable in dimension 4 when the number of tiles is held fixed at three: no algorithm can take an arbitrary set of three connected polyhypercubes (connected finite unions of unit hypercubes) and decide whether their translated copies tile $\\mathbb{Z}^4$. This improves the frontier from four tiles in dimension 4, and it is a step toward the open conjecture that some fixed dimension may already have an undecidable monotile version of the same problem. The proof reduces Wang's domino problem to the three-tile tiling problem, so a decision procedure for the latter would solve the former. A second theorem establishes the same undecidability in dimension 3 with four tiles, and the 4D result is obtained by lifting that 3D construction through a time-slicing technique.","feed_headline":"Three tiles make 4D translational tiling undecidable","feed_subtitle":"A reduction from Wang's domino problem leaves no algorithm for three connected 4D polyhypercubes","key_machinery":"The carrying mechanism is a translation of Wang tilings into tiling constraints on three families of 4D tiles. The encoder is a thick 3D encoder whose color bits are stored by two spacetime building blocks, $C^{(4)}$ and $D^{(4)}$; the linker is a rigid frame that can only occupy positions on a lattice in space while remaining free to slide in the time direction; the filler is the single building block $c^{(4)}$. The load-bearing identity is Fact 2 from the 3D proof: in every tiling, the representative points of the linkers lie exactly on the lattice $\\{(10x,60y,20pz) \\mid x,y,z\\in\\mathbb{Z}\\}$. In the 4D proof, the analogous rigidity requires each time slice to contain the same rigid lattice and the same encoder distribution, enforced by the building block $E^{(4)}$. The time-slicing lift is what replaces the two 3D linker types—$U$-linker and $D$-linker—by a single linker that shifts along the fourth dimension, reducing the tile count from four to three.","core_discovery":"The paper's central claim, on its own terms, is that translational tiling with three connected polyhypercubes in $\\mathbb{Z}^4$ is undecidable. The proof gives an explicit reduction: from any finite set of Wang tiles it builds a set of three tiles—an encoder, a linker, and a filler—such that the three-tile set tiles $\\mathbb{Z}^4$ exactly when the Wang set tiles the plane. Encoding layers of the encoders reproduce the color-matching constraints of Wang tiles, while the linker tiles are forced into a rigid lattice whose gaps determine which encoding layer acts as the matching layer. The 3D version of the construction uses four tiles, comprising two linker types instead of one, establishing Theorem 2. Consequently, any algorithm that decided the three-tile problem in dimension 4 would also decide Wang's domino problem, which is known to be undecidable.","pith_inferences":["The rigidity assertions (Fact 2 and its 4D analogue) are stated without a full derivation; a reader who wants to verify the proof should focus there. If a computer search on finite tori could produce a linker configuration not on the stated lattice with all encoders still matched, the reduction's equivalence would fail as written, though it might be repairable by altering block shapes.","The single-linker time-sliding idea suggests a route toward two-tile undecidability in dimension 5 or higher: lift the encoder's alignment constraints to yet another dimension so one tile plays both the encoder and linker roles, matching the authors' closing remark that they are two steps from a monotile.","Because Wang tile sets can have arbitrarily many tiles, the construction implies that three-tile 4D tilings can encode computations of arbitrary finite size; consequently no local, finite-window criterion can characterize whether such a tile set tiles the space.","The same dimension-for-tiles tradeoff might be pushed further: the paper's 3D construction uses two linker types, and any 3D mechanism that merged them into one would establish 3D undecidability with three tiles as well."],"forward_implications":["No algorithm can decide whether an arbitrary set of three connected polyhypercubes tiles $\\mathbb{Z}^4$; the existence of such an algorithm would decide Wang's domino problem.","The known undecidable boundary for translational tilings drops to three tiles in dimension 4 and to four tiles in dimension 3.","The two theorems sharpen the evidence for the conjecture that a fixed dimension may already admit an undecidable monotile translational tiling problem, because the construction trades one dimension for one tile: dimension 4 with three tiles lifts dimension 3 with four tiles.","Every tiling produced by the reduction is forced, in matching layers, to simulate a tiling by the original Wang tile set, so any concrete Wang tile set that tiles the plane yields a concrete three-tile 4D tiling, and vice versa."],"supporting_citations":[{"why":"Berger's theorem that Wang's domino problem is undecidable provides the source problem from which the reduction starts.","marker":"[2]"},{"why":"The paper's 3D construction refines this earlier 3D polycube tiling framework; it supplies the encoder/linker layer technique being sharpened.","marker":"[23]"},{"why":"The lifting technique that converts a 3D tiling into a 4D tiling in one fewer tile is taken from this work; the paper's Section 3 relies on it explicitly.","marker":"[24]"}],"fun_headline_variants":["Three connected tiles prove 4D tiling undecidable","No algorithm for 4D tiling with 3 connected tiles","4D tiling with three tiles is undecidable","Three polyhypercubes make 4D tiling undecidable","From Wang tiles: 4D 3-tile tiling undecidable"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the asserted rigidity of the linker packing: every valid tiling must put linker representative points exactly on the lattice $\\{(10x,60y,20pz)\\}$ in 3D, and in 4D must keep the same rigid lattice and encoder distribution in every time slice. If any alternative packing of linkers exists, the reduction's equivalence with Wang tilings breaks.","fun_headline_variants_meta":{"raw":{"variants":["Three connected tiles prove 4D tiling undecidable","No algorithm for 4D tiling with 3 connected tiles","4D tiling with three tiles is undecidable","Three polyhypercubes make 4D tiling undecidable","From Wang tiles: 4D 3-tile tiling undecidable"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00038,"raw_usage":{"total_tokens":1999,"prompt_tokens":905,"completion_tokens":1094,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":521,"completion_tokens_details":{"reasoning_tokens":1002}},"tokens_in":521,"tokens_out":1094,"duration_ms":7524,"temperature":1.0,"reasoning_tokens":1002,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T15:45:03.164645+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Look for a valid tiling of $\\mathbb{Z}^4$ by the three constructed tiles whose linker representative points are not all on the lattice $\\{(10x,60y,20pz)\\}$, or in which two time slices have different encoder arrangements. A targeted way to search is to tile a finite torus whose side lengths are multiples of the construction's periods; any solution that does not descend to a Wang tiling of the matching layer would falsify the rigidity step on which the reduction rests.","supporting_citations":[{"cited_title":"Berger, The undecidability of the domino problem, Memoirs of the American Mathematical Society , 66(1966), 1-72","cited_arxiv_id":null,"evidence_quote":"Berger's theorem that Wang's domino problem is undecidable provides the source problem from which the reduction starts."},{"cited_title":"Undecidability of Translational Tiling of the 4-dimensional Space with a Set of 4 Polyhypercubes","cited_arxiv_id":"2409.00846","evidence_quote":"The lifting technique that converts a 3D tiling into a 4D tiling in one fewer tile is taken from this work; the paper's Section 3 relies on it explicitly."}],"review_version":1}