Pith. sign in

REVIEW 2 major objections 5 minor 1 cited by

Two Tiling is Undecidable

T0 review · 2 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read Given two polygonal prototiles, deciding whether they tile the plane is undecidable, improving the previous three-tile bound.

desk verdict Plausible two-tile undecidability with a genuinely new construction, but the completeness direction rests on an unproven converse and Lemma 17 has a missing angle case; deserves serious refereeing, not acceptance yet. read the letter →

arxiv 2506.11628 v1 pith:XO7KGZQG submitted 2025-06-13 cs.CG math.COmath.MG

Jack Stade This is my paper · ORCID
classification cs.CGmath.COmath.MG MSC 52C2005B45
keywords undecidabilitytilingprototilesedge-to-edgematchingrulesmonotilingWangtilespolyominoescomputationalgeometry
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 tries to establish that the geometric tiling problem is undecidable even when the input consists of only two polygonal prototiles, improving a previously known bound of three tiles. It also proves a companion result: if edge-to-edge matching rules are allowed, one prototile already gives an undecidable tiling problem, the first such monotiling undecidability under only local matching constraints. The proof routes Wang tiling through an intermediate AB tiling problem, then into weave-pattern tilings by a single stick-shaped polyhex tile, and finally into two real polygonal tiles by adding a small staple tile that simulates the matching rules. If the proof is right, no algorithm can decide two-tile tilability, and the boundary between decidable and undecidable tile counts is pushed down as far as this method allows.

What carries the argument

The central object is a stick prototile made of n hexagons, realizable as a polyhex, together with a list of forbidden edge pairings that force any tiling into a weave pattern: a diagonal grid of horizontal and slanted stacks of sticks. The argument's movable mechanism is the tiling schematic, in which each horizontal stack becomes a block, gaps between blocks carry left and right values, and the matching rules become arrow and triangle markings on block edges. The gap conditions, constraints on states, left and right values, and how they change across rows, make the schematic programmable: they simulate the AB tiling dynamics in the same way that rules on Wang tiles simulate a computation. The second key object is the staple tile, a small regular 12-gon; bumps and dents cut into the stick edges ensure that legal edge pairings leave holes the staple fills, while illegal pairings overlap bumps, converting matching rules into pure geometry.

What would settle it

For a small Wang tile set, implement the reduction and check a finite patch: enumerate all gap-condition assignments on a finite diagonal lattice and test whether each can be aligned into a schematic; a single assignment that satisfies Lemmas 7-9 but cannot be realized geometrically would refute the completeness direction and force a repair of the reduction that the two-tile theorem depends on.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1: there is no algorithm that, given two polygonal prototiles, decides whether rotated and translated copies of them tile the plane. The theorem is proved through Theorem 2, which says the same problem is undecidable for a single prototile when edge-to-edge matching rules forbid certain edge pairs. The reduction chain is: Wang tiling reduces to AB tiling, a parity-constrained tiling by two families of 1x2 rectangles; AB tiling reduces to tilings by a stick of n hexagons that local matching rules force into a weave pattern; and a weave pattern is compressed into a schematic whose rows of blocks and gaps satisfy explicit gap conditions. The two-tile theorem follows by modifying the stick's edges with bumps and dents and adding a small staple tile so that every legitimate edge match leaves spaces exactly fillable by the staple, while forbidden matches create overlapping bumps. The author also notes the construction yields undecidability of translational 4-tiling and sketches how the same ideas give undecidability with three polyomino prototiles.

Load-bearing premise

The proof depends on an unproved converse in Section 2.5: that every assignment of states and values to the diagonal lattice of gaps satisfying the gap conditions actually gives a valid schematic and hence a real tiling; if that converse fails, the reduction from AB tilings to stick tilings is incomplete.

Editorial extensions

If this is right

  • Two polygonal prototiles are sufficient to make the plane-tiling decision problem undecidable, lowering the known tile count from three to two.
  • A single prototile with edge-to-edge matching rules has an undecidable tiling problem, so local matching constraints alone do not restore decidability to monotiling.
  • The construction uses four total tile orientations, so translational 4-tiling is undecidable; since translational monotiling is decidable, only the two- and three-tile translation cases remain open.
  • The same technique is sketched to give undecidability with three polyomino prototiles, improving the previous five-polyomino bound.
  • The reduction is robust to whether reflections are allowed, because the stick can be modified so reflected copies can never sit next to each other.

Reading between the lines

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

  • Editorial: the weave-pattern scaffolding treats the plane as a programmable lattice, so the same gap-condition machinery may transfer to other decision problems where a few geometric objects must simulate a computation, not just tiling.
  • Editorial: making the Section 2.5 converse fully explicit would turn the proof into a constructive compiler from Wang tile sets to concrete polygon coordinates, making the undecidability reduction directly testable on finite patches.
  • Editorial: if the three-polyomino sketch can be completed rigorously, the only remaining gap between decidable and undecidable polyomino tilability would be two polyominoes, close to the one-tile case that is still open.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 5 minor

Summary. The paper claims that the following problem is undecidable: given two polygonal prototiles, determine whether the plane can be tiled with rotated and translated copies of them. This would improve the recent three-tile undecidability result of Demaine and Langerman. The proof proceeds by first proving a stronger intermediate statement: with edge-to-edge matching rules, a single prototile has an undecidable tiling problem. The construction reduces from Wang tiling via AB tiling, encodes AB tilings as "weave patterns" of stick-shaped polyhexes, abstracts these tilings into row schematics with states and values governed by local "gap conditions," and then uses a small staple tile to simulate the edge-to-edge matching rules geometrically. The paper also states consequences for translational tiling and sketches a three-polyomino analogue.

Significance. If the proofs are completed as claimed, Theorem 1 is a genuine quantitative improvement (from three to two polygonal prototiles) for a long-studied undecidability question in tiling theory, and Theorem 2 is the first undecidability result for monotiling under purely local edge-to-edge matching constraints. The reduction is self-contained: it is anchored in the independent undecidability of AB tiling, it defines all constants explicitly (such as d=12k and v=(2t+1)d), and it addresses both directions of the main biconditional. The schematic/gap-condition framework is a useful abstraction that could be reused. However, one load-bearing converse direction is currently asserted without proof, so the central result is not yet fully established.

major comments (2)
  1. [2.5] The claim at the end of Section 2.5 that "any assignment of the states, left values, and right values to a diagonal lattice of gaps that satisfies the gap conditions corresponds to a valid schematic (and so to a valid tiling)" is asserted without proof; the text defers the verification with "These calculations are essentially no different from the ones in the proofs of Lemmas 6 to 9, so we will not include them here." This is a load-bearing step, not a cosmetic omission: the AB-tiling-to-stick-tiling direction of Theorem 15 (Section 2.9) constructs only states and values via Lemmas 11 and 13 and then invokes this converse to obtain a geometric tiling. The gap conditions constrain the algebraic quantities locally, but they do not, as written, establish that row offsets can be chosen consistently around cycles, that adjacent rows overlap by at least one unit, or that every gap end lands on the prescribed triangle and arrow marks. Please supply the missing proof, for example by an inductive construction of the row offsets and a verification that the overlap and marking requirements follow from the value-difference constraints in Lemma 9.
  2. [2.1] The proof of Lemma 4 contains an unexpanded key step: after showing that every left-leaning stack has two stacks above and two below, it states "It remains to check that the left-leaning stacks forms a grid. Specifically... But this is straightforward." This commutation property is part of the definition of a weave pattern and is what justifies the passage to the row-schematic representation used in Section 2.3 and throughout the reduction. Since the second direction of Theorem 15 starts from an arbitrary valid tiling and extracts a schematic, the grid property must be verified explicitly rather than deferred as straightforward. Please either provide the local case analysis or state and prove the missing lemma.
minor comments (5)
  1. [2.5] There are several typos and grammatical slips that should be corrected: "Any of assignment" (Section 2.5), "vise versa" (Section 2.3), "undecideable" (Theorem 15), and "polyonimo" (Section 4).
  2. [2.9] In the proof of Theorem 15, the sentence "the B tile with lower-left corner is the one represented by gap (e1 - sr, 2c + 1)" is missing the coordinates of the lower-left corner; it should specify (2c+1, 2r+1) or the equivalent.
  3. [3] Lemma 16 is stated without proof; a short argument that a regular 12-gon cannot tile the plane on its own would make the staple construction self-contained.
  4. [2.1] The proof of Lemma 4 relies heavily on visual case analysis in Figures 6-18; a text enumeration of the forbidden local configurations would help verification and would avoid the need to infer cases from the figures.
  5. [4] The three-polyomino undecidability result is presented only as a sketch; the text should state explicitly which parts are complete and which remain to be supplied.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the reduction chain runs from Wang/AB tiling through an explicit geometric encoding; the §2.5 converse is an omitted proof, not a circular step.

full rationale

The paper's derivation chain is not circular. Theorem 2 reduces monotiling with edge-to-edge matching rules to AB tiling, which is reduced in Lemma 5 from the standard undecidable Wang tiling problem via an explicit S-tetromino encoding. The stick-tile construction is self-contained: the weave pattern is enforced by explicit forbidden edge pairings (rules 1-11, Lemma 4), and the schematic representation is built from explicit geometric objects (blocks, gaps, buckets, triangle and arrow marks) with stated positions. Lemmas 6-9 derive the gap conditions from the geometry rather than assuming the target result; Lemmas 10-14 and Theorem 15 then translate between AB tilings and schematics by explicit value assignments. No parameter is fitted to data and no equation is definitionally equal to its input: the constants d = 12k, v = (2t+1)d, and s = 16+8(t-1) are instance-dependent construction choices, not fitted quantities. The staple-tile simulation in Section 3 is likewise geometric, using angle sums to argue that modified sticks and staples simulate matching rules, with the forbidden-pair bump/dent construction making the iff argument concrete rather than presupposed. The weakest passage is Section 2.5, where the converse of the gap conditions is asserted: 'any of assignment of the states, left values, and right values to a diagonal lattice of gaps that satisfies the gap conditions corresponds to a valid schematic (and so to a valid tiling)', with the justification deferred to 'calculations essentially no different from the ones in the proofs of Lemmas 6 to 9'. This is a genuine completeness gap in the AB-to-schematic direction, and it should be flagged as a proof omission, but it is not circularity: the converse is not used as an input to the construction, it is not a renamed version of an assumption, and it does not make the undecidability claim reduce to itself. The paper also cites Demaine and Langerman for the prior three-tile result and for the staple-tile idea, and cites Berger, Ollinger, and Yang-Zhang for baseline undecidability results; these citations are external support, not self-citations, and none is load-bearing in place of the paper's own construction. Overall, the central claim has independent content and the reduction is self-contained against an established undecidable problem; the appropriate score is 0.

Assumptions & free parameters 6 free parameters · 4 assumptions · 3 invented entities

The construction's constants are instance-dependent design choices rather than data-fitted parameters; they are listed to make the design decisions explicit. The axioms are standard geometric facts plus the external Wang undecidability result. No entity is postulated without a concrete definition and an internal proof of its role.

free parameters (6)
  • d = 12k = 12k, where k is the number of AB/Wang colors
    Chosen in Section 2.8 to separate tile-index constraints from color-matching constraints; the 6k and 12k offsets in the L and R sets depend on it.
  • v = (2t+1)d = (2t+1)*12k
    Number of left and right values per state, sized so encoding states can represent 2t tile indices with d-spacing.
  • s = 16 + 8(t-1) = 16 + 8(t-1), where t = |A| = |B|
    Number of buckets/states; fixed so the state cycle synchronizes with the AB tiling structure and the four encoding states.
  • bucket length l_b = (2v-1)(s-1) + 2v = instance-dependent
    Set in Section 2.5 so the gap-length bounds in Lemmas 6 through 9 work out exactly.
  • encoding state indices e1=1, e1.5=5, e2=9, e3=9+4(t-1), e4=17+4(t-1) = as listed
    Chosen spacing for the encoding states; the spacing of 4(t-1) makes the tile-index propagation in Lemma 12 work.
  • gadget interval families for I_i and L_i = [−d+1,1], [−1,d−1], [0,6k], and the shifted L sets in Section 2.7
    Hand-chosen intervals controlling how much left and right values may change between rows; they define the allowed paths in Figures 35 through 37.
assumptions (4)
  • standard math The Wang tiling problem is undecidable (Berger 1966).
    Base of the reduction chain: AB tiling reduces from Wang tiling (Lemma 5), and the stick construction reduces from AB tiling.
  • standard math In any tiling of the plane, the angles of tiles meeting at a point sum to 2π.
    Used in Lemma 17 to classify which corners can meet after the staple modification; the enumeration of angle sums is the backbone of that lemma.
  • standard math A regular 12-gon cannot tile the plane by itself (Lemma 16).
    The staple tile must not tile independently, otherwise the modified two-tile tiling could avoid sticks entirely; the proof cites the standard fact that only triangles, squares, and hexagons among regular polygons tile the plane.
  • domain assumption Edge-to-edge matching rules are well defined for partial edge contacts in the weave pattern.
    The rule list in Section 2.1 and the staple simulation in Lemma 17 assume forbidden pairs apply to any contact between the named edge types, including partial contacts; the bump-spot alignment that would enforce this is asserted but not fully shown.
invented entities (3)
  • Stick prototile (chain of n hexagons with labeled edges) independent evidence
    purpose: Single prototile whose tilings encode AB tilings via weave-pattern forcing and gap conditions.
    Explicit geometric object defined in Section 2.1; its encoded behavior is proven internally (Lemmas 4-15) and is directly checkable in a tiling program.
  • Staple prototile (regular 12-gon with diameter smaller than 1/(8n+4) of an edge length) independent evidence
    purpose: Second prototile that simulates edge-to-edge matching rules geometrically via bumps and dents.
    Explicit shape defined in Section 3; Lemmas 16 and 17 give its key properties. It is a concrete geometric object, not an unexplained postulate.
  • AB tiling framework (1x2 rectangles with parity placement and edge colors) independent evidence
    purpose: Intermediate undecidable problem that bridges Wang tiles and the stick construction.
    Defined in Section 2.2; Lemma 5 reduces Wang tiling to it. The encoding is explicit and can be tested against known Wang instances.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Two Tiling is Undecidable." pith.science (2026). https://pith.science/paper/XO7KGZQG

@misc{pith2026250611628,
  author       = {Pith},
  title        = {Pith review of: Two Tiling is Undecidable},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XO7KGZQG}},
  note         = {Machine review of arXiv:2506.11628}
}
read the original abstract

We show that the following problem is undecidable: given two polygonal prototiles, determine whether the plane can be tiled with rotated and translated copies of them. This improves a result of Demaine and Langerman [SoCG 2025], who showed undecidability for three tiles. Along the way, we show that tiling with one prototile is undecidable if there can be edge-to-edge matching rules. This is the first result to show undecidability for monotiling with only local matching constraints.

Figures

Figures reproduced from arXiv: 2506.11628 by the authors.

Figure 1
Figure 1. A stick of length 6. Horizontal Slant left Slant right [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. The orientations of a stick (up to rotations by [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Stacked pairs leaning left and right. The direction that a pair leans is invariant under [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗
Figures from the paper (45 more)
Figure 4
Figure 4. Figure 4: The weave pattern that the sticks should form. • All the sticks are either horizontal or slant left • There is a horizontal stick • All the horizontal sticks are in left-leaning stacks (called the horizontal stacks) and all the left-slanted sticks are in right-leaning …
Figure 5
Figure 5. Figure 5: Preventing these arrangements of tiles will force a tiling to form a weave pattern. Note [PITH_FULL_IMAGE:figures/full_fig_p006_5.png]
Figure 6
Figure 6. Figure 6: Trying to place a stick next to a stacked pair when the stick doesn’t slant in the same [PITH_FULL_IMAGE:figures/full_fig_p007_6.png]
Figure 7
Figure 7. Figure 7: A stack of height more than n introduces a pair violating rule 4 (highlighted in purple) 7 [PITH_FULL_IMAGE:figures/full_fig_p007_7.png]
Figure 8
Figure 8. Figure 8: If a horizontal stick is placed next to a left-slanted stick, then all of the concave vertices [PITH_FULL_IMAGE:figures/full_fig_p008_8.png]
Figure 9
Figure 9. Figure 9: A left leaning stack can’t have height exactly [PITH_FULL_IMAGE:figures/full_fig_p008_9.png]
Figure 10
Figure 10. Figure 10: If T slants right, then the space below S must be filled by a left-leaning stack. Now we can argue that the space marked B in Figures 11 and 15 must be filled by a horizontal stick U that meets some, but not all, of the concave corners on the back side of S. The space…
Figure 11
Figure 11. Figure 11: If T slants right, then the space below S must be filled by a left-leaning stack, as in the bottom-right figure. 9 [PITH_FULL_IMAGE:figures/full_fig_p009_11.png]
Figure 12
Figure 12. Figure 12: The space marked A in [PITH_FULL_IMAGE:figures/full_fig_p010_12.png]
Figure 13
Figure 13. Figure 13: T must be a horizontal stick, facing downwards, that meets some, but not all, of the concave corners on the back side of S. T T S S [PITH_FULL_IMAGE:figures/full_fig_p010_13.png]
Figure 14
Figure 14. Figure 14: The space right of T must contain a left-slanted stick. 10 [PITH_FULL_IMAGE:figures/full_fig_p010_14.png]
Figure 15
Figure 15. Figure 15: T is the bottom of a left-leaning stack. S S S T T T [PITH_FULL_IMAGE:figures/full_fig_p011_15.png]
Figure 16
Figure 16. Figure 16: The space B must also be filled by a horizontal stick meeting some, but not all, of the concave corners on the back side of S. We use the presence of the stack containing T to make this conclusion. 11 [PITH_FULL_IMAGE:figures/full_fig_p011_16.png]
Figure 17
Figure 17. Figure 17: Every left-leaning stack has two left-leaning stacks meeting its back side. [PITH_FULL_IMAGE:figures/full_fig_p012_17.png]
Figure 18
Figure 18. Figure 18: Every left leaning stack has 4 adjacent left-leaning stacks—two on the front side and [PITH_FULL_IMAGE:figures/full_fig_p013_18.png]
Figure 19
Figure 19. Figure 19: The pattern that an AB tiling should make. [PITH_FULL_IMAGE:figures/full_fig_p013_19.png]
Figure 20
Figure 20. Figure 20: A set of Wang tiles (upper left) can be simulated by a set of AB tiles (upper middle). [PITH_FULL_IMAGE:figures/full_fig_p014_20.png]
Figure 21
Figure 21. Figure 21: A section of a weave pattern tiling together with a schematic representation. [PITH_FULL_IMAGE:figures/full_fig_p015_21.png]
Figure 22
Figure 22. Figure 22: The forbidden configurations represented by an arrow marking. [PITH_FULL_IMAGE:figures/full_fig_p016_22.png]
Figure 23
Figure 23. Figure 23: The ends of a block in the row above can only occur above a triangle marking facing in [PITH_FULL_IMAGE:figures/full_fig_p017_23.png]
Figure 24
Figure 24. Figure 24: An example of the type of constraint that can be created with arrow and triangle [PITH_FULL_IMAGE:figures/full_fig_p017_24.png]
Figure 25
Figure 25. Figure 25: The block is divided into a number of equally-sized buckets. The boundary between [PITH_FULL_IMAGE:figures/full_fig_p018_25.png]
Figure 26
Figure 26. Figure 26: A block with 3 buckets. Bucket i can only fit below a gap with left length i and right length 4 − i. Each row has gaps that only fit above the next bucket in the cycle, so the rows cycle through the states. Lemma 6. Each gap is contained in one of the buckets in the r…
Figure 27
Figure 27. Figure 27: If two adjacent gaps in a row occur above different buckets in the row below, then there [PITH_FULL_IMAGE:figures/full_fig_p019_27.png]
Figure 28
Figure 28. Figure 28: Specification of a bucket. The specific example illustrated is the [PITH_FULL_IMAGE:figures/full_fig_p020_28.png]
Figure 29
Figure 29. Figure 29: Calculating the possible left and right lengths for a gap in state [PITH_FULL_IMAGE:figures/full_fig_p021_29.png]
Figure 30
Figure 30. Figure 30: A stick with s = 3 and v = 3, split into three rows with one bucket on each row. Each Li , Ri , and Ii is chosen to be as large as possible, that is Li = Ri = {1, 2, 3} and Ii = {−2, −1, 0, 1, 2}. Above each bucket are drawn arrows representing the possible left and r…
Figure 31
Figure 31. Figure 31: Calculations for Lemma 9 By Lemma 7, the left side of a gap in state i has left length (2v − 1)(σ(i) − 1) + x for some x ∈ Ri ⊆ {1, . . . , v}. The inequalities (2v−1)(j−1)−v+2 ≤ (2v−1)(σ(i)−1)+x ≤ (2v−1)(j−1)+2v−1 can only be satisfied when σ(i) = j. So if a row is i…
Figure 32
Figure 32. Figure 32: If a gap is in an odd row, then the one below it to the left is in the same column. If a [PITH_FULL_IMAGE:figures/full_fig_p023_32.png]
Figure 33
Figure 33. Figure 33: The encoding states e1 through e4 correspond to different parts of an AB tiling. States e1 and e2 go through the upper parts of the A tiles and the lower parts of the B tiles, while states e3 and e4 go through the lower parts of the A tiles and the upper part of the B…
Figure 34
Figure 34. Figure 34: Illustration of Lemma 10. 2.7 Creating the AB pattern In this section, we describe the states between e2 and e3. The states between e4 and e1 can be created in an analogous way. Recall that e2 is an encoding state, so has Le2 = {dj : 1 ≤ j ≤ 2t}. If (r + e2, c) is in …
Figure 35
Figure 35. Figure 35: Each vertical tick represents one of the values in [PITH_FULL_IMAGE:figures/full_fig_p026_35.png]
Figure 36
Figure 36. Figure 36: In order to fill in a single column in the states between [PITH_FULL_IMAGE:figures/full_fig_p027_36.png]
Figure 37
Figure 37. Figure 37: The analogous diagram to Figure [PITH_FULL_IMAGE:figures/full_fig_p028_37.png]
Figure 38
Figure 38. Figure 38: The gaps between e1 and e2 and between e3 and e4 are each split in half. Proof. Consider some even j, so 1 ≤ vj ≤ t and t + 1 ≤ vj−1, vj+1 ≤ 2t by assumption [PITH_FULL_IMAGE:figures/full_fig_p029_38.png]
Figure 39
Figure 39. Figure 39: Filling in the columns j and j + 1 when vj represents an A tile. In the figure, a = vj and b = vj+1. Note that ca = cb by assumption, so 12k(2t + 1 − a) + 2k + cb − ca is in Re1+2. (12kb|12k(2t + 1 − b)) (12ka| . . .) (. . . |12kb + 4k + cb) (12k(2t + 1 − b) − 4k − cb…
Figure 40
Figure 40. Figure 40: Filling in the columns j−1 and j when vj represents and A tile. In the figure, a = vj and b = vj+1. The colors ca and cb might not match, which is okay because 12k(2t+ 1−b)−2k +ca −cb is in Re1+2. 30 [PITH_FULL_IMAGE:figures/full_fig_p030_40.png]
Figure 41
Figure 41. Figure 41: A regular 12-gon [PITH_FULL_IMAGE:figures/full_fig_p032_41.png]
Figure 42
Figure 42. Figure 42: A dent (left) or a bump (right). by gap (e1 − sr, 2c + 1). By Lemma 14, the colors match along vertical edges, so this forms a valid AB tiling. So T tiles the plane if and only if S does. By Lemma 5, this proves the claim. 3 Simulating matching rules geometrically We …
Figure 43
Figure 43. Figure 43: Three edges with dents and bumps. Here the prohibited pairs are (1 [PITH_FULL_IMAGE:figures/full_fig_p033_43.png]
Figure 44
Figure 44. Figure 44: The allowed pairs (1, 1), (1, 2), and (2, 3) from the example in [PITH_FULL_IMAGE:figures/full_fig_p033_44.png]
Figure 45
Figure 45. Figure 45: The prohibited pairs (1, 3), (2, 2) and (3, 3) from the example in [PITH_FULL_IMAGE:figures/full_fig_p034_45.png]
Figure 46
Figure 46. Figure 46: We can further modify each edge of the stick so that a reflected tile can never be placed [PITH_FULL_IMAGE:figures/full_fig_p034_46.png]
Figure 47
Figure 47. Figure 47: Top: a block tile and a gap tile. Middle: a section of a schematic made with block tiles [PITH_FULL_IMAGE:figures/full_fig_p035_47.png]
Figure 48
Figure 48. Figure 48: Realizing our construction with polyhexes. First, we need to increase the resolution of [PITH_FULL_IMAGE:figures/full_fig_p036_48.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Undecidability of Translational Tiling with 2 Polycubes

    math.CO 2025-08 conditional novelty 8.0 of 10

    The translational tiling problem for Z^3 is undecidable even for a set of two connected polycubes.

Reference graph

Works this paper leans on

12 extracted references · 6 canonical work pages · cited by 1 Pith paper

  1. [1]

    The undecidability of the domino problem

    Robert Berger. The undecidability of the domino problem. Mem. Amer. Math. Soc. , 66:72, 1966

    work page 1966

  2. [2]

    Tiling with three polygons is undecidable

    Erik Demaine and Stefan Langerman. Tiling with three polygons is undecidable. In 41st International Symposium on Computational Geometry (SoCG 2025) , Leibniz International Proceedings in Informatics (LIPIcs), Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz- Zentrum f¨ ur Informatik. To appear. URL:https://arxiv.org/abs/2409.11582. 36

    arXiv 2025

  3. [3]

    Girault-Beauquier and M

    D. Girault-Beauquier and M. Nivat. Tiling the plane with one tile. In Proceedings of the Sixth Annual Symposium on Computational Geometry , SCG ’90, page 128–138, New York, NY, USA, 1990. Association for Computing Machinery. doi:10.1145/98524.98553

    arXiv 1990

  4. [4]

    Solomon W. Golomb. Tiling with sets of polyominoes. Journal of Combinatorial The- ory, 9(1):60–71, 1970. URL: https://www.sciencedirect.com/science/article/pii/ S0021980070800552, doi:10.1016/S0021-9800(70)80055-2

    work page doi:10.1016/s0021-9800(70)80055-2 1970

  5. [5]

    Open questions in tiling

    Chaim Goodman-Strauss. Open questions in tiling. 01 2000. URL: https://strauss.hosted. uark.edu/papers/survey.pdf

    work page 2000

  6. [6]

    On the undecidability of the tiling problem

    Jarkko Kari. On the undecidability of the tiling problem. In Viliam Geffert, Juhani Karhum¨ aki, Alberto Bertoni, Bart Preneel, Pavol N´ avrat, and M´ aria Bielikov´ a, editors,SOFSEM 2008: Theory and Practice of Computer Science , pages 74–82, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg

    work page 2008

  7. [7]

    Two-by-two substitution systems and the undecidability of the domino prob- lem

    Nicolas Ollinger. Two-by-two substitution systems and the undecidability of the domino prob- lem. In Arnold Beckmann, Costas Dimitracopoulos, and Benedikt L¨ owe, editors, Logic and Theory of Algorithms , pages 476–485, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg

    work page 2008

  8. [8]

    Tiling the plane with a fixed number of polyominoes

    Nicolas Ollinger. Tiling the plane with a fixed number of polyominoes. In Adrian Horia Dediu, Armand Mihai Ionescu, and Carlos Mart ´ ın-Vide, editors,Language and Automata Theory and Applications, pages 638–647, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg

    work page 2009

Show all 12 references
  1. [9]

    Robinson

    Raphael M. Robinson. Undecidability and nonperiodicity for tilings of the plane. Inventiones mathematicae, 12(3):177–209, 1971. doi:10.1007/BF01418780

    1971 doi

  2. [10]

    Kaplan, and Chaim Goodman-Strauss

    David Smith, Joseph Samuel Myers, Craig S. Kaplan, and Chaim Goodman-Strauss. An aperiodic monotile. Combinatorial Theory , 4(1), July 2024. URL: http://dx.doi.org/10. 5070/C64163843, doi:10.5070/c64163843

    2024 doi

  3. [11]

    Kaplan, and Chaim Goodman-Strauss

    David Smith, Joseph Samuel Myers, Craig S. Kaplan, and Chaim Goodman-Strauss. A chiral aperiodic monotile. Combinatorial Theory, 4(2), September 2024. URL: http://dx.doi.org/ 10.5070/C64264241, doi:10.5070/c64264241

    2024 doi

  4. [12]

    Translational tiling with 8 polyominoes is undecidable

    Chao Yang and Zhujun Zhang. Translational tiling with 8 polyominoes is undecidable. Dis- crete and Computational Geometry , November 2024. URL: http://dx.doi.org/10.1007/ s00454-024-00706-1 , doi:10.1007/s00454-024-00706-1 . 37

    2024 doi

Pith tools

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