RECORD
The aperiodic Domino problem in higher dimension
Discrete Mathematics · Submitted 15 Feb 2022
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim We show that it is much harder, namely analytic ($\Sigma_1^1$-complete), in higher dimension: $d \geq 4$ in the finite type case, $d \geq 3$ for sofic and effective subshifts.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
The classical Domino problem asks whether there exists a tiling in which none of the forbidden patterns given as input appear. In this paper, we consider the aperiodic version of the Domino problem: given as input a family of forbidden patterns, does it allow an aperiodic tiling? The input may correspond to a subshift of finite type, a sofic subshift or an effective subshift. arXiv:1805.08829 proved that this problem is co-recursively enumerable ($\Pi_0^1$-complete) in dimension 2 for geometrical reasons. We show that it is much harder, namely analytic ($\Sigma_1^1$-complete), in higher dimension: $d \geq 4$ in the finite type case, $d \geq 3$ for sofic and effective subshifts. The reduction uses a subshift embedding universal computation and two additional dimensions to control periodicity. This complexity jump is surprising for two reasons: first, it separates 2- and 3-dimensional subshifts, whereas most subshift properties are the same in dimension 2 and higher; second, it is unexpectedly large.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | The classical Domino problem asks whether there exists a tiling in which none of the forbidden patterns given as input appear. | background 1.00 | 0.04 | 0.02 | asserted 0.93 |
| s1 | In this paper, we consider the aperiodic version of the Domino problem: given as input a family of forbidden patterns, does it allow an aperiodic tiling? | contribution 0.56 | 0.35 | 0.04 | asserted 0.58 |
| s2 | The input may correspond to a subshift of finite type, a sofic subshift or an effective subshift. arXiv:1805.08829 proved that this problem is co-recursively enumerable ($\Pi_0^1$-complete) in dimension 2 for geometrical reasons. | background 1.00 | 0.07 | 0.04 | asserted 0.90 |
| s3 | We show that it is much harder, namely analytic ($\Sigma_1^1$-complete), in higher dimension: $d \geq 4$ in the finite type case, $d \geq 3$ for sofic and effective subshifts. | result 0.97 | 0.95 | 0.91 | asserted 1.00 |
| s4 | The reduction uses a subshift embedding universal computation and two additional dimensions to control periodicity. | method 1.00 | 0.86 | 0.04 | asserted 1.00 |
| s5 | This complexity jump is surprising for two reasons: first, it separates 2- and 3-dimensional subshifts, whereas most subshift properties are the same in dimension 2 and higher; second, it is unexpectedly large. | interpretation 1.00 | 0.60 | 0.07 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
The classical Domino problem asks whether there exists a tiling in which none of the forbidden patterns given as input appear. In this paper, we consider the aperiodic version of the Domino problem: given as input a family of forbidden patterns, does it allow an aperiodic tiling? The input may correspond to a subshift of finite type, a sofic subshift or an effective subshift. arXiv:1805.08829 proved that this problem is co-recursively enumerable ($\Pi_0^1$-complete) in dimension 2 for geometrical reasons. We show that it is much harder, namely analytic ($\Sigma_1^1$-complete), in higher dimension: $d \geq 4$ in the finite type case, $d \geq 3$ for sofic and effective subshifts. The reduction uses a subshift embedding universal computation and two additional dimensions to control periodicity. This complexity jump is surprising for two reasons: first, it separates 2- and 3-dimensional subshifts, whereas most subshift properties are the same in dimension 2 and higher; second, it is unexpectedly large.
Human review
How the literature uses it
1 arXiv paper cite this in 1 sentence
Papers citing it
Cites it as background 1 paper
-
Regarding the arithmetical hierarchy, the Domino problem is $Π_1$-complete [ref] , the conjugacy problem is $Σ_1$-complete and the factorisation problem is $Σ_3$-complete [ref] … Regarding the analytical hierarchy, deciding whether a tiling has a completely positive topological entropy or not is $Π_1^1$-complete [ref] , in dimension $d≥4$ the aperiodic Domino problem is $Π_1^1$-complete [ref] … To obtain these results, the proofs always involve the embedding of Turing machines into complex (and aperiodic) tilings.
Arithmetical Hierarchy of the Besicovitch-Stability of Noisy Tilings · Introduction · 0.90
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.