# The aperiodic Domino problem in higher dimension

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.

[Grandjean-Hellouin-Vanier 2018] 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.

Such difficulty jumps in decision problems for subshifts usually occur between dimensions 1 and 2; it was unexpected for us to find this jump in higher dimension and with such a large difficulty gap.