{"id":"43c2f62b-10d6-4ee9-adc3-852f7372f86d","arxiv_id":"2506.19295","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Translational tiling of the plane with a set of four (disconnected) polyominoes is undecidable.","lead":"This paper proves that deciding whether the whole plane can be tiled by translated copies of four oddly shaped tiles is impossible in general. The result improves the known bound from five tiles to four, using a construction that codes Wang tile colors with a single connector.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Arithmetic mismatch in Section 3: the distance between matching encoder portions is L+t, not L, so the central alignment invariant in Section 4 fails.","rationale":"The reader's weakest_assumption correctly identifies Section 4's unproven rigidity assertions, but my stress-test sharpens this: the failure is not merely a missing case analysis but a concrete arithmetical contradiction in the construction. Section 3 computes the encoder padding so that same-slot portions are 'exactly the length of the locator' apart, yet the displayed formulas give A+P = 2^{3n}(t+2)-t-1, i.e., L+t. For the paper's own example this is 2045 versus 2043. Since slot offsets change by multiples of t+2 = 4, no pair of slots can be 2043 apart in the encoder as specified. This is not an exotic tiling behavior; it is the intended placement itself that is impossible. The central isomorphism between tilings of the four polyominoes and Wang tilings is therefore not established. There is no code or formal verification to fall back on, and the proof is explicitly a sketch. I do not claim the theorem is false; the construction may be repairable by changing the padding to L-A, and the three-copy redundancy idea is plausible. But as written, the proof of Theorem 1.3 has a hole at its load-bearing joint, so the manuscript should not be accepted in its current form. The reader's verdict should move from CONDITIONAL to REJECT of the current version.","tokens_in":10010,"tokens_out":21054,"duration_ms":196779,"concrete_test":"For n=3, m=4, t=2, test the identity that the distance between matching encoding portions equals the locator length. Compute A = 2^{3n-1}(t+2) = 1024, P = 2^{3n-1}(t+2)-t-1 = 1021, and L = 2^{3n}(t+2)-2t-1 = 2043. Verify that A+P = 2045, so the identity fails. Then try the corrected padding P' = L-A = 1019; recompute the encoder total length and verify that for any two slots k and l, A+P'+(l-k)(t+2) = L implies k=l. Also check that the locator's concave-part length and the requirement that at least one slot remain outside are still consistent. If the corrected formulas restore the invariant, the proof may be salvageable; otherwise the reduction itself is invalid.","verdict_should_be":"REJECT","load_bearing_attack":"The proof's key invariant is that the two exposed pieces of an encoder in the locator lattice are the left and right portions of the same simulated Wang tile. This invariant is falsified by the paper's own size arithmetic. For the example with n=3, m=4, t=2, the locator length is L = 2^{3n}(t+2)-2t-1 = 2043. The encoder's left and right encoding segments have length A = 2^{3n-1}(t+2) = 1024, and the padding is P = 2^{3n-1}(t+2)-t-1 = 1021. The distance between the start of a slot in the left segment and the start of the corresponding slot in the right segment is A+P = 2045, not 2043. In general this distance is 2^{3n}(t+2)-t-1, i.e., L+t. For the two exposed windows to be exactly L apart, the slot indices would have to satisfy (k-l)(t+2)=t, which has no integer solution. Therefore no horizontal shift of an encoder can place two portions of the same simulated Wang tile at the positions fixed by the rigid locator lattice. The subsequent 'three copies and pigeonhole' argument in Section 4 cannot select a non-overlapping placement, so the reduction to Wang tilings fails as written. The error appears to be a factor of t in the padding formula; correcting it would also change the concave-part length and the locator equation, so the entire size calculation in Section 3 needs rechecking.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":10311,"tokens_out":22971,"duration_ms":228247,"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":[{"comment":"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.","section":"§4, \"The locators form a rigid lattice pattern\""},{"comment":"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.","section":"§4, \"The locators and the encoders can be compatible\""},{"comment":"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.","section":"§3, encoder size calculations"}],"minor_comments":[{"comment":"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.","section":"Introduction and Section 2"},{"comment":"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.","section":"Section 2"},{"comment":"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.","section":"Throughout"},{"comment":"The caption contains a typo: '2043 builiding blocks' should be '2043 building blocks'.","section":"Figure 8"},{"comment":"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.","section":"Section 5"}],"recommendation":"major_revision","confidential_remarks":"The paper is a natural next step in a competitive line of work and the core reduction idea is plausible. However, the proof of Theorem 1.3 is currently a detailed sketch rather than a complete rigorous argument, and the distance convention in Section 3 needs to be clarified before the construction can be checked. I would be willing to reconsider after the authors supply the missing case analyses and rewrite the relevant paragraphs as formal lemmas. The disconnected-tile caveat should also be made prominent so that the comparison with prior connected-tile results is not overstated."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague—\n\nThe stress-test note misses the mark on the arithmetic. It computes A+P = L+t for the separation between slot starts and concludes the central invariant fails. But the paper's \"distance between the encoding building blocks\" is the gap between the t encoding blocks of the two portions, not the distance between slot starts. With the marker/encoding layout, that gap is A+P−t, which equals the locator length L by the padding formula. Check the example: A+P = 2045, t = 2, so the gap is 2043, exactly as the paper claims. The slot-index equation (k−l)(t+2)=t in the stress-test is irrelevant; it comes from comparing slot starts. The invariant is sound.\n\nWhat is actually new: a single linker instead of the usual two, plus unequal-distance placement and triple encoding of each Wang tile. These shrink the tile count from 5 to 4. The construction is explicit, scales with the Wang tile set, and has no fitted parameters—it is a genuine many-one reduction. The paper honestly notes the tiles may be disconnected and that the connected case remains open.\n\nThe real weakness is Section 4, which is a sketch. \"The locators form a rigid lattice pattern\" is asserted in a few sentences, not proved by case analysis. This rigidity is load-bearing: if any tiling could dodge the lattice, the equivalence with Wang tilings would break. The three-copies pigeonhole argument for avoiding overlaps between adjacent encoders is plausible but not fully derived; the row-by-row construction needs a clearer proof that the chosen locations never cause conflicts globally. The gap-filling claim is also passed off with \"it is easy to check.\" None of this is clearly wrong, but it is underspecified for a result of this kind.\n\nI think the result is likely correct and the contributions are real. The paper deserves a serious referee, but the referee should push for a complete case analysis in Section 4, maybe with computer-checked local configurations. I'd accept it for peer review and request revision rather than desk-reject.\n\nBest.","headline":"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.","tokens_in":10816,"tokens_out":8557,"would_cite":true,"duration_ms":75962,"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 the plane with a set of four polyominoes is undecidable, by a reduction from Wang's domino problem.","keywords":["translational tiling","polyomino","undecidability","Wang tiles","domino problem","fixed number of tiles","disconnected polyomino"],"falsifier":"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.","tokens_in":9814,"feed_emoji":"🧩","tokens_out":5460,"duration_ms":53380,"temperature":0.7,"pith_summary":"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.","feed_headline":"Four polyominoes make plane tiling undecidable","feed_subtitle":"A four-tile reduction from Wang's domino problem closes the gap from five tiles to four.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"The result that Wang's domino problem is undecidable; this is the source problem from which the paper's reduction transfers undecidability.","marker":"[3]"},{"why":"Supplies the fixed-tile reduction framework and the original proof for 11 polyominoes; the present construction refines this template.","marker":"[9]"},{"why":"Provides the plus-shape tiny filler shape and the previous best bound of five polyominoes, both reused here.","marker":"[8]"},{"why":"The earlier proof that seven polyominoes suffice, establishing the reduction lineage this paper continues.","marker":"[16]"},{"why":"The single-tile periodicity characterization used to conclude that the tiny filler cannot tile the plane by itself.","marker":"[2]"},{"why":"Formulates Wang's domino problem, the decision problem from which undecidability is transferred.","marker":"[11]"}],"fun_headline_variants":["Four tiles prove plane tiling undecidable","Undecidability with only four polyominoes","Four polyominoes seal undecidability of tiling","Plane tiling undecidable via four-tile set"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Four tiles prove plane tiling undecidable","Undecidability with only four polyominoes","Four polyominoes seal undecidability of tiling","Plane tiling undecidable via four-tile set"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000506,"raw_usage":{"total_tokens":2409,"prompt_tokens":828,"completion_tokens":1581,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":444,"completion_tokens_details":{"reasoning_tokens":1513}},"tokens_in":444,"tokens_out":1581,"duration_ms":12807,"temperature":1.0,"reasoning_tokens":1513,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T18:34:06.743742+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Berger, The undecidability of the domino problem,Memoirs of the American Mathemat- ical Society,66(1966), 1-72","cited_arxiv_id":null,"evidence_quote":"The result that Wang's domino problem is undecidable; this is the source problem from which the paper's reduction transfers undecidability."},{"cited_title":"Ollinger, Tiling the plane with a fixed number of polyominoes, In: A.H","cited_arxiv_id":null,"evidence_quote":"Supplies the fixed-tile reduction framework and the original proof for 11 polyominoes; the present construction refines this template."},{"cited_title":"Beauquier, M","cited_arxiv_id":null,"evidence_quote":"The single-tile periodicity characterization used to conclude that the tiny filler cannot tile the plane by itself."},{"cited_title":"Wang, Proving theorems by pattern recognition-II,Bell System Technical Journal, 40(1961) 1-41","cited_arxiv_id":null,"evidence_quote":"Formulates Wang's domino problem, the decision problem from which undecidability is transferred."}],"review_version":2}