Tiling 3D Space by (Translates of) a Single Polycube is Undecidable

arXiv:2610.12392 · cs.CG, math.CO, math.MG · Submitted 2026-10-08 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "Tiling 3D Space by (Translates of) a Single Polycube is Undecidable".

Jane: Here's the gist of the paper. Tiling 3D by translates of a single polycube is co-RE-complete and hence undecidable.

Tom: This paper proves co-RE-completeness, and thus undecidability, of the problem: given a single (connected) polycube, decide whether it tiles 3D Euclidean space by translations.

Jane: Problem Definition and Context The core question addressed is whether deciding if a finite set of prototiles can tile the entire integer lattice in a given dimension is decidable.

Tom: The authors focus specifically on the case where there is only one prototile and the space is 3D, showing this problem is undecidable.

Title and authors: Tom: So we're looking at this paper today, "Tiling three dee Space by (Translates of) a Single Polycube is Undecidable," and the main takeaway is that deciding if one specific shape, or polycube, can tile all of three dimensional space by just shifting it around with translations is actually undecidable <ref:2610.12392#pg1,by (Translates of) a Single Polycube is Undecidable>.

Jane: Undecidable how does that sound? It means there's no algorithm we can ever write that will look at any given polycube and tell us for sure if it *can* tile the whole space or if it absolutely cannot >

Lu: Yeah, so what this paper proves is co-RE-completeness for this problem, which means every other problem in the co-RE class can be reduced to tiling three dee space by a single polycube <ref:2610.12392#pg2> >

Meng: So, if it's co-RE-complete, that suggests it's incredibly hard, which is what we expected from these kinds of tiling problems with complex constraints >

Tom: Exactly. But the real meat of this paper is how they prove that connection through a reduction from the Wang tiling problem.

Jane: That sounds like it’s taking something we already know is impossible to solve and mapping it onto this three dee polycube question > <ref:2610.12392#pg1>

Lu: Right, they use five different reductions to map those finite sets of Wang tiles into a single connected three dee prototile <ref:2610.12392#pg1>. They adapt stuff from Greenfeld and Tao, incorporate an encoding from OpenAI, and then apply reductions from Meyerovitch et al. to change the target space >

Jane: So they are essentially building a very complicated three dee shape out of the Wang tiles in such a way that if this three dee shape could tile space by translation, it would imply you could solve the original Wang tiling problem, which we know is impossible > <ref:2610.12392#pg1>

Tom: That's the core idea. And what they highlight is that dimension three is actually optimal for this kind of undecidability result because translational monotiling in two dimensions and for a single polyomino in R two is known to be decidable <ref:2610.12392#pg1>.

Meng: So, the implication for us on the engineering side is that we can stop wasting time trying to find a general solver for this kind of tiling problem because it's fundamentally impossible >

Title and authors: Jane: That’s a big shift from just thinking about whether a specific shape tiles something simple, to realizing there are certain geometric constraints where the very question itself doesn't have an answer >

Lu: And they back up the proof with formal verification in Lean four which is pretty rigorous; they checked that these definitions and theorem statements in a single file accurately express the claim <ref:2610.12392#pg6> >

Tom: That leans on their own work with formal methods, which is interesting because it shows that even for something this abstract as tiling, you can get this level of certainty using these tools >

Jane: So, the paper shows that this isn't just a theoretical curiosity; they’ve managed to make the proof checkable by formalizing it in Lean four and checking only a few key definitions > <ref:2610.12392#pg1>

Meng: I wonder what the practical implications are beyond just proving undecidability. If we ever try to build something where these constraints are involved, we should know from now on that brute-forcing or trying to find a simple pattern won't work for the whole space >

Tom: Definitely. It’s about knowing when to stop looking for a simple solution and when you have to accept the fundamental limits of what can be decided algorithmically >

Jane: So, moving on from the proof structure, they detail how this result fits into a larger table showing tiling complexity across different numbers of prototiles and dimensions <ref:2610.12392#pg2> >

Lu: That table shows how co-RE-complete this problem is for different numbers of tiles and dimensions, highlighting that three dimensional translational monotiling is one of the hardest cases in that list >

Meng: It’s interesting to see how they categorize it against problems like tiling with four or five polyominoes, which are also co-RE-complete, but this paper focuses specifically on the single polycube case <ref:2610.12392#pg2> >

Tom: And what they emphasize is that the blue highlight in that table shows their new result for the single tile case in three dimensions, which establishes it as co-RE-complete >

Jane: So, it solidifies this finding: given a single connected polycube, deciding if it tiles three dimensional Euclidean space by translations is undecidable <ref:2610.12392#pg1> >

Title and authors: Lu: And they mention that the proof relies on specific constructions, like adapting OpenAI’s cyclic tiling encoding to handle those Wang tile constraints and the nonconstant column conditions simultaneously <ref:2610.12392#pg3> >

Meng: That adaptation seems key because it’s how they manage to force those complex Wang tile rules into the structure of a three dee prototile without making it disconnected > <ref:2610.12392#pg1>

Tom: And I think that connection is what makes this paper so compelling; they're taking established undecidability from one area and building a complicated reduction to show it holds here >

Jane: It’s like they’re showing that the difficulty of solving the Wang tiling problem is robust enough to carry over when we move into three dee translation tiling, even with just one tile > <ref:2610.12392#pg1>

Lu: And looking ahead, the paper points toward these reductions as a general method for proving undecidability in similar geometric tiling scenarios <ref:2610.12392#pg3> >

Meng: I hope that method gets applied to problems where we are trying to design physical packing arrangements, because knowing it's undecidable means we can’t rely on finding a simple mathematical formula for all cases >

Tom: It means for these kinds of problems, the focus needs to shift from finding a perfect algorithm to understanding the inherent boundaries of what is computable >

Jane: So, to wrap up this segment, the paper "Tiling three dee Space by (Translates of) a Single Polycube is Undecidable" shows that despite being just one tile in three dimensions, the problem remains fundamentally undecidable because it can simulate the complexity of known impossible problems like Wang tiling > <ref:2610.12392#pg1,by (Translates of) a Single Polycube is Undecidable>

Lu: And I think this result provides a strong formal foundation for why we have to be careful when we design systems involving these types of spatial constraints <ref:2610.12392#pg1> >

Meng: For my team, it means if we ever run into a constraint satisfaction problem where the solution space involves infinite translational possibilities, we should assume it’s undecidable >

Tom: It sounds like we have a very firm boundary here for what's computable in this specific geometric domain.

Jane: And that brings us to wrapping up this discussion on how these tiling problems push the limits of what we can decide computationally.

The paper's summary: Tom: So, we've been looking at how this paper proves that tiling three dimensional space by just shifting one single polycube is undecidable <ref:2610.12392#pg1>. Now, to make sure we're all on the same page, what does co-RE-complete actually mean in plain English for someone listening right now?

Jane: It means that if you give an AI a single polycube and ask it to decide if it can tile the whole space by translation, there is no general program you can write that will give a correct yes or no answer for every single possible polycube. It's not just hard; it's fundamentally impossible to solve with an algorithm.

Lu: That’s right. The paper shows this problem is co-RE-complete, which means we can reduce other problems we already know are impossible, like the Wang tiling problem, onto this three dee tiling question <ref:2610.12392#pg3>. It's a very strong way to show the difficulty.

Meng: So you’re saying they took a problem where you just try to arrange colored tiles on a flat plane and showed that if you could do that, you could solve this three dee space tiling thing, which is impossible. That's what I mean, it's a huge jump in difficulty level.

Tom: Exactly. And the authors didn't just say it was hard; they used formal verification in Lean four to check their proof. That’s like them building a digital proof checker to ensure their logic holds up, which is pretty impressive for something so abstract.

Jane: It gives us this concrete confidence in the result, Tom, because they formalized the entire argument into a single file and ran it through an AI assistant to make sure every step of the reduction was solid. That removes a lot of doubt about whether their conclusion is just a lucky guess.

Lu: Their method involves adapting constructions from Greenfeld and Tao, mixing in some cyclic encodings from OpenAI, and using reductions from Meyerovitch et al. to set up this complicated mapping between the Wang tiles and the three dee shape. It’s a very intricate assembly process for building that impossible tile.

Meng: That sounds like a lot of moving parts just to get one single polycube built, which makes sense because they are trying to encode all those complex rules of the Wang tiles into that one shape. If they made it disconnected, the problem might be easier, but keeping it connected adds another layer of complexity.

Tom: And what this really changes for us in AI and modeling is realizing that when we design systems involving spatial constraints or packing problems, we can’t just rely on finding a simple pattern to solve them completely. We have to accept that there are inherent limits to what an algorithm can ever decide about those arrangements.

Jane: So, the implication here is more than just math theory; it means if you're working on anything that involves fitting things together in three dimensions, whether it's physical packing or some kind of computational structure, you need to be aware that a perfect solver isn't going to exist for every case.

Lu: And they point out the complexity table, which shows how this single polycube case fits into the landscape of tiling problems across different numbers of prototiles and dimensions, confirming its place as one of the hardest ones in that category.

Meng: So, it’s not just a theoretical impossibility; it’s a verified impossibility for this specific setup. It tells us where the boundary is for what we can compute about space tiling.

The paper's improvements: Tom: So we've been talking about how this paper proves that tiling three dimensional space by just shifting one single polycube is undecidable, and now we're looking at what they suggest to fix or improve on that result. What are the practical next steps they’re hinting at?

Jane: They aren't actually proposing a new algorithm because the whole point is that no such algorithm exists for this problem, but their suggestion is more about how we approach the proof itself and what we can learn from it. They focus on making the reduction process clearer and more robust.

Lu: They highlight that they used formal verification in Lean four, which means they are pushing the boundaries of how rigorously you can prove these kinds of undecidability results using AI tools to check their work. It shows a new way to build trust in complex mathematical proofs.

Meng: From an engineering standpoint, what I hear is that if we ever try to model physical packing problems where translations are involved, we should expect the complexity ceiling they’ve set here. We can stop trying to find a magical solver for those specific constraints.

Tom: Right, they mention adapting constructions from different researchers like Greenfeld and Tao and incorporating things like OpenAI’s cyclic encodings again in their discussion of the reduction steps. It’s not just one path; it shows that you can use these different tools to force the problem into this undecidable structure regardless of how you frame it.

Jane: They are suggesting that instead of just showing one way to map Wang tiles to this shape, they show how different mathematical ideas can be combined—like using a particular encoding or reduction technique—to achieve the same impossible result. It’s like having a toolbox full of impossibilities and finding a way to use them all together.

Lu: The implication for future work is that these reduction techniques are powerful enough to apply to other tiling problems, not just this one specific case of three dimensional space with one polycube. It suggests a general blueprint for proving undecidability in geometric settings.

Meng: If they can create a general blueprint, that means we might be able to predict which types of spatial constraints will lead to undecidability before we even start building the system. That’s valuable for risk assessment on production systems, I guess.

Tom: It moves the conversation from "can we solve this?" to "what kind of structure leads us into this undecidable zone?" It’s a shift in focus from solving the problem to understanding its fundamental limits.

Jane: So, they aren't giving us a way around it, but they are giving us a better map of why we can't just brute-force our way through these spatial puzzles. This is about learning the landscape of what’s computable.

Conclusion: Tom: So we’re wrapping up on "Tiling three dee Space by (Translates of) a Single Polycube is Undecidable." The main point is that this specific problem, deciding if one single polycube can tile three dimensional space by translation, is mathematically proven to be undecidable.

Jane: That means no matter how smart an algorithm you design for it, it will eventually run into a case where it just won't know the answer because the problem is fundamentally too hard.

Lu: The paper establishes this by showing a co-RE-completeness, which basically means this tiling problem is as hard as some of the most complex problems we already know are impossible to solve algorithmically.

Meng: If you’re looking at designing physical systems where components have to fit together like that, you just have to assume there’s no simple formula that will ever solve it perfectly for all possible shapes.

Lalam: I’m confident in this answer; the proof structure is very solid, relying on established undecidability results and a rigorous formalization process using Lean four. It’s a very sure answer.

Tom: And the fact that they formalized the whole thing to be checked by an AI assistant adds a layer of certainty we don't always get in pure math papers. That kind of verification is what makes this result really stick with me as an engineer.

Jane: It’s about seeing how deep these fundamental limits go, Tom, and it shows us that even when dealing with just one tile in three dimensions, the computational boundary is extremely high.

Lu: The implication for future work is that these reduction techniques are a general method for proving undecidability in similar geometric tiling scenarios across different dimensions and tile sets.

Meng: If they can build a general method, then we might be able to predict which types of spatial constraints will lead us into this undecidable zone before we even start designing the system.

Tom: So it’s not just about solving this one problem; it’s about understanding the boundaries of what computers can ever compute when dealing with spatial arrangements.

Jane: Exactly, and that moves our focus from finding a perfect solver to understanding the inherent limits of what's computable in these geometric domains.

Lu: We'll be looking at other papers soon that touch on representation learning and how AI agents navigate complex systems, which should connect nicely to these kinds of undecidability proofs.

Massachusetts Institute of Technology · Université Libre de Bruxelles

cs.CG, math.CO, math.MG

Submitted: 2026-10-08

Updated: 2026-11-13

Comments: 10 pages, 2 figures, 2 tables, 15 snippets. Added rotation/reflection results and corresponding table

Code: https://github.com/edemaine/lean-wang

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 88/100

The gist: Tiling 3D by translates of a single polycube is co-RE-complete and hence undecidable.

Key concepts

Co-RE-Completeness
This complexity class describes problems where a 'no' answer can be verified in finite time by an algorithm. A problem is co-RE-complete if it is at the hardest level within this class, meaning every other problem in this class can be reduced to it.
Polycube Tiling
This refers to determining if a single, connected 3D shape (a polycube) can perfectly cover all of 3D space when moved only by rigid translations. The paper focuses on whether one specific polycube can tile the entire integer lattice ($\mathbb{Z}^3$)
Reduction Strategy
The proof uses a reduction to show that if you could solve the polycube tiling problem, you could also solve the undecidable Wang tiling problem. This involves constructing a complex 3D prototile from a finite set of Wang tiles.

Terminology

Summary

Tiling 3D by translates of a single polycube is co-RE-complete and hence undecidable. p. 0 This paper proves co-RE-completeness, and thus undecidability, of the problem: given a single (connected) polycube, decide whether it tiles 3D Euclidean space by translations. p. 0

Problem Definition and Context

The core question addressed is whether deciding if a finite set of prototiles can tile the entire integer lattice in a given dimension is decidable. The authors focus specifically on the case where there is only one prototile and the space is 3D, showing this problem is undecidable. p. 0 This result builds upon historical context where similar tiling problems were studied in 2D and lower dimensions. p. 1

Reduction Strategy

The proof establishes co-RE-hardness by reducing the well-known Wang tiling problem to the 3D polycube tiling problem. The construction involves combining five different reductions to map a finite set of Wang tiles into a single, connected 3D prototile. p. 2 These steps include adapting constructions from Greenfeld and Tao, incorporating OpenAI’s cyclic encoding, and applying reductions from Meyerovitch et al. p. 0 to change the target space. p. 2

Formal Verification

The mathematical rigor of the proof is established through formal verification using Lean 4. The authors formalized the proof in Lean, building on prior formalizations of Wang tiling undecidability. p. 2 The verification relies on checking a handful of definitions and theorem statements in a single file, Abstract. p. 3lean, which is then verified by the Lean proof assistant. p. 0

Key Theorems and Results

The paper culminates in two main theorems establishing the undecidability results. Theorem 1.1 states that tiling Z cubed by translations of a single finite connected subset of Z cubed is co-RE-complete and hence undecidable. p. 0 Furthermore, the paper shows that tiling R cubed by translations of the solid body of a single finite connected polycube is also co-RE-complete and undecidable. p. 4 These results are supported by four specific Lean theorems in Section 3. p. 4

Acknowledgments and Resources

The research heavily utilized AI tools for finding, writing, and formalizing the proof. The complete technical article and the full Lean code are available in the repository [DL26b] for further study. p. 5 The paper was typeset with Texlish, and specific LLM models were used in the process. p. 5

References

The work draws upon numerous prior results concerning tiling problems across different dimensions and tile sets. Key cited works include Golomb’s implementation of Wang tiling [Gol70], and various results from Greenfeld and Tao, Kim, Yan, and others regarding translational tilings in Z d. p. 0 The paper cites references such as [Ber66] for the undecidability of Wang tiling and [Kim26] for translational tiling with two polycubes. p. 5 It also references work on periodicity in Z d, like [Bha20] and results concerning the structure of translational tilings in Z d, such as [GT21]. p. 5 The final list includes references for specific constructions and undecidability proofs across various dimensions and tile types.

--- Page 7 ---

[MSS25] Tom Meyerovitch, Shrey Sanadhya, and Yaar Solomon. A note on reduction of tiling problems. p. 6 Israel Journal of Mathematics, 267:421–435, 2025. p. 6 Numbered references use arXiv:2211. p. 5 p. 507140v1.

[Oll09] Nicolas Ollinger. p. 6 Tiling the plane with a fixed number of polyominoes. p. 6 In Language and Automata Theory and Applications (LATA 2009), volume 5457 of Lecture Notes in Computer Science, pages 638–647. p. 6 Springer, 2009. p. 6

[Ope26] OpenAI. p. 2 A translational tile with no fully periodic tiling in dimension three. p. 6 Preprint, September 23, 2026. p. 6 Versioned preprint on GitHub, accessed October 7, 2026. p. 6

[Wan61] Hao Wang. p. 6 Proving theorems by pattern recognition—II. p. 6 Bell System Technical Journal, 40(1):1–41, 1961. p. 6 Bell Labs archive. p. 6

[Bha20] Siddhartha Bhattacharya. p. 5 Periodicity and decidability of tilings of Z squared. p. 5 American Journal of Mathematics, 142(1):255–266, 2020. p. 5 arXiv:1602. p. 505738v1.

[Dem26] Erik D. p. 5 Demaine. lean-wang: Lean 4 formalization of Wang tiling and the domino problem. p. 5 GitHub repository, 2026. p. 5 https://github. p. 5com/edemaine/lean-wang. p. 5

[DL26a] Erik D. p. 5 Demaine and Stefan Langerman. p. 0 p. 0 Texlish: Better LATEX. p. 5 Software, version 0. p. 52.0, 2026, https://texlish. p. 5org/.

[DL26b] Erik D. p. 5 Demaine and Stefan Langerman. translation-tiling-paper: Tiling 3D by translates of a single polycube is undecidable. p. 5 GitHub repository, 2026, https://github. p. 5com/edemaine/translation-tiling-paper. p. 5

[Gol70] Solomon W. p. 5 Golomb. Tiling with sets of polyominoes. p. 5 Journal of Combinatorial Theory, 9(1):60–71, 1970. p. 5

[GT21] Rachel Greenfeld and Terence Tao. p. 5 The structure of translational tilings in Z d. p. 5 Discrete Analysis, (16):1–28, 2021. p. 5 arXiv:2010. p. 503254v3.

[GT24] Rachel Greenfeld and Terence Tao. p. 5 A counterexample to the periodic tiling conjecture. p. 5 Annals of Mathematics, 200(1):301–363, 2024. p. 5 Numbered references use arXiv:2211.15847v3.

[GT25] Rachel Greenfeld and Terence Tao. p. 5 Undecidability of translational monotilings. p. 5 Journal of the European Mathematical Society, 2025. p. 5 Online first. p. 5 Numbered references use arXiv:2309. p. 509504v2.

[Kim25] Yoonhu Kim. p. 5 Undecidability of tiling the plane with a set of 5 polyominoes, 2025. p. 5 arXiv:2508. p. 5 p. 510067v1.

[Kim26] Yoonhu Kim. p. 5 Undecidability of translational tiling with 2 polycubes, 2026. p. 5 Version 2, August 10, 2026. p. 5 Numbered references use arXiv:2508. p. 511725v2.

[MIT25] MIT–ULB CompGeom Group, Zachary Abel, Hugo Akitaya, Lily Chung, Erik D. p. 5 Demaine, Jenny Diomidova, Della Hendrickson, Stefan Langerman, and Jayson Lynch. p. 5 Undecidability of tiling with a tromino, 2025. p. 5 arXiv:2509. p. 507906v1.

[YZ25a] Chao Yang and Zhujun Zhang. p. 6 On the undecidability of tiling the 3-dimensional space with a set of 3 polycubes, 2025. p. 6 In Chinese. p. 6 arXiv:2508.00192v1.

[YZ25b] Chao Yang and Zhujun Zhang. p. 6 Undecidability of translational tiling of the 3-dimensional space with a set of 6 polycubes. p. 6 Proceedings of the American Mathematical Society, 153(8):3541–3554, 2025. p. 6 arXiv:2408. p. 602196.

[YZ26a] Chao Yang and Zhujun Zhang. p. 6 Translational aperiodic sets of 7 polyominoes. p. 6 Science China Mathematics, 2026. p. 6 To appear. Originally arXiv:2412. p. 617382.

[YZ26b] Chao Yang and Zhujun Zhang. p. 6 Translational tiling with 8 polyominoes is undecidable. p. 6 Discrete & Computational Geometry, 75(4):1048–1059, 2026. p. 6 Originally arXiv:2403. p. 613472.

[Yan23] Chao Yang. p. 6 Tiling the plane with a set of ten polyominoes. p. 6 International Journal of Computational Geometry & Applications, 33(03n04):55–64, 2023. p. 6

[Yan25] Chao Yang. p. 6 On the undecidability of tiling the plane with a set of nine polyominoes (in Chinese). p. 6 SCIENCE CHINA Mathematics (Chinese Edition) [SCIENTIA SINICA Mathematica], 55(6):1113–1122, 2025. p. 6

[YZ25c] Chao Yang and Zhujun Zhang. p. 6 Undecidability of translational tiling of the plane with four tiles. p. 6 arXiv:2506. p. 6 p. 619295, 2025. p. 6

[YZ25d] Chao Yang and Zhujun Zhang. p. 6 Undecidability of translational tiling with orthogonally convex polyominoes. p. 6 arXiv:2506.12726, 2025. p. 6

--- Page 1 ---

Tiling 3D by Translates of a Single Polycube is Undecidable Erik D. Demaine∗ Stefan Langerman† Abstract We prove co-RE-completeness, and thus undecidability, of the following problem: given a single (connected) polycube, decide whether it tiles 3D Euclidean space by translations. p. 0 p. 0

The proof is verified in Lean. p. 0 See Section 4 for details of our approach, and the repository [DL26b] for the complete Lean code and a longer LLM-written technical article. p. 0

--- Page 2 ---

Translations only Prototiles 1D 2D 3D dD (d ≥ 4) R (↓) R [Bha20, GT21] co-RE-c (Thm. 1.1)∗ co-RE-c (←) R OPEN co-RE-c [Kim26] (↑) co-RE-c (↑) R co-RE-c [MIT25] co-RE--coR[YZ25a, MIT25] (↑) coR(↑)∗

Table 1: Complexity of tiling the whole integer lattice by translations with possibly disconnected polycubes, organized as in [MIT25, Table 3]. Rows bound the number of prototiles; n means an arbitrary finite input set. p. 1 The last column applies to every fixed d ≥ 4. p. 1 Co-RE is the complexity class of decision problems whose “no” instances can be recognized in finite time by an algorithm (Turing machine). p. 1 A problem is co-RE-hard if every co-RE problem can be reduced to it via a computable many-one reduction, and co-RE-complete if it is also in co-RE. p. 1 It is known that some co-REcomplete problems (such as “does a given algorithm run forever? p. 1”) are undecidable, so co-RE-completeness implies undecidability. p. 1

--- Page 3 ---

1Connectivity of a set in Z cubed is defined according to lattice adjacency in Z cubed. Connectivity of a polycube in R cubed is thus defined according to face adjacency of the constituent unit cubes. p. 0 See Section 3. p. 02.

--- Page 4 ---

The solid body of P is the union of the closed unit cubes p + [0, 1] cubed for p ∈ P.

--- Page 5 ---

def Adjacent (a b: Point): Prop:= I i, a i - b i = 1.

def Connected (P: Prototile): Prop:= ∀ p ∈ P, ∀ q ∈ P, Relation. p. 3ReflTransGen (fun a b => a ∈ P ∧ b ∈ P ∧ Adjacent a b) p q. p. 3

def Tiles (P: Prototile): Prop:= ∃ T: Set Point, ∀ x: Point, ∃! p. 3 t: Point, t ∈ T ∧ x - t ∈ P. p. 0

--- Page 6 ---

The proof of Theorem 1.1 is long and technical. p. 2 To make it checkable, we formalized it in the Lean 4 proof assistant, building on Mathlib and on the formalization of Wang tiling undecidability (lean-wang [Dem26]). p. 2 The key point is that a reader does not need to read the proof, or even most of the definitions, to trust the result: it suffices to check that the handful of definitions and theorem statements in a single file, Abstract. p. 3lean, accurately express the claim. p. 3

--- Page 1 ---

Tiling 3D by Translates of a Single Polycube is Undecidable Erik D. Demaine∗ Stefan Langerman† Abstract We prove co-RE-completeness, and thus undecidability, of the following problem: given a single (connected) polycube, decide whether it tiles 3D Euclidean space by translations.

--- Page 2 ---

Translations only Prototiles 1D 2D 3D dD (d ≥ 4) R (↓) R [Bha20, GT21] co-RE-c (Thm. 1.1)∗ co-RE-c (←) R OPEN co-RE-c [Kim26] (↑) coR(↑)∗

--- Page 3 ---

1Connectivity of a set in Z cubed is defined according to lattice adjacency in Z cubed.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Enhanced proof verification capability: The system can perform formal verification using Lean 4 to check complex proofs, as detailed in Section 3 of the paper, ensuring that claims like Tiling Z3 by translations of a single finite connected subset of Z3 is co-RE-complete are rigorously established.

  2. Automated reduction construction: The AI system can be equipped with algorithms capable of constructing the computable map described in Section 2, which reduces Wang tiling to the polycube tiling problem, thereby automating the complex five-step reduction process involving Greenfeld and Tao constructions and cyclic encodings.

  3. Knowledge base integration for complexity classification: The system can integrate Table 1 from Section 2 into its knowledge base to rapidly classify problems based on dimension (d) and number of prototiles (k), allowing for instant identification of known decidable versus co-RE-complete problems.

  4. Formalization of connectivity and tiling definitions: The AI can be trained to understand the formal definitions provided in Section 3, such as A prototile is a finite list P of points in Z3 and P tiles Z3 if there exists a set T subset of Z3 of translations such that every x in Z3 lies in exactly one translate t + P.

Sources

Related papers