In the 1960s, Berger famously showed that translational tilings of \mathbb{Z}^{2} with multiple tiles are algorithmically undecidable. Recently, Bhattacharya proved the decidability of translational monotilings (tilings by translations of a single tile) in \mathbb{Z}^{2} . The decidability of translational monotilings in higher dimensions remained unsolved. In this paper, by combining our recently developed techniques with ideas introduced by Aanderaa–Lewis, we finally settle this problem, achieving the undecidability of translational monotilings of (periodic subsets of) virtually \mathbb{Z}^{2} spaces, namely, spaces of the form \mathbb{Z}^{2}\times G_{0} , where G_{0} is a finite Abelian group. This also implies the undecidability of translational monotilings in \mathbb{Z}^{d} , d\geq 3 .
This paper presents a significant breakthrough in the field of tiling theory by demonstrating the algorithmic undecidability of translational monotilings in higher dimensions (Zᵈ for d ≥ 3) and in “virtually Z² spaces” (Z² × G₀, where G₀ is a finite Abelian group). This resolves a long-standing open problem regarding the decidability of tiling by a single prototile (monotiling) in dimensions beyond two.
The significance of this work lies in extending the boundaries of algorithmic undecidability from more complex tiling scenarios to the simplest one involving a single tile under translational symmetry in higher dimensions. Previously, Berger famously showed that the problem of deciding whether a given finite set of multiple tiles can tile the plane (Z²) is undecidable (the Wang tiling problem). More recently, Bhattacharya proved that for translational monotilings in Z², the problem is decidable. This paper bridges the gap, showing that while translational monotilings are decidable in 2D, they become undecidable in 3D and higher, fundamentally altering the landscape of what is algorithmically computable in tiling problems.
The key innovations driving this result are a sophisticated chain of reductions, building on and combining established and recent techniques:
Reduction from Wang Tilings to Domino Functions: The paper begins by generalizing the well-known undecidable Wang tiling problem to what they call the “R-domino problem.” A Wang tiling, which involves placing colored unit squares according to edge-matching rules, can be directly translated into an R-domino problem, where a “domino function” assigns ‘pips’ to cells on a Z² grid, satisfying rules for horizontal and vertical adjacencies. Since Wang tiling is undecidable, the R-domino problem is also undecidable. This provides the foundational source of algorithmic intractability.
Introduction of Decorated p-adic Sudoku Puzzles: This is a crucial intermediate step and a major innovation. The undecidable R-domino problem is then encoded into a novel construct: a “decorated p₁ × p₂-adic Sudoku puzzle.” This generalization of the Sudoku puzzle uses p-adic analysis (number systems based on prime numbers p), inspired by ideas from Aanderaa and Lewis. The “decoration” aspect means that beyond the p-adic structure constraining how digits are placed, the puzzle also carries information that directly simulates the behavior of the domino function from the previous step. The highly structured nature of p-adic Sudoku solutions allows for the precise encoding of the complex, undecidable rules of the domino problem. Solutions to these puzzles are shown to exist if and only if the corresponding R-domino problem is solvable, thus transferring the undecidability.
Encoding Sudoku Puzzles as Translational Monotiling Problems: The final, critical step leverages the authors’ previously developed “tiling language” (from prior works like GT21, GT22). This language provides a framework to express abstract combinatorial properties of functions (like those governing Sudoku puzzle solutions) as concrete translational monotiling problems. By showing that the decorated p-adic Sudoku puzzle is “weakly expressible” in this tiling language, the paper demonstrates that a translational monotiling exists if and only if the Sudoku puzzle has a solution. This completes the chain, proving the undecidability of the target problem.
Main Prior Ingredients Needed: