Antonin Callard (ENS Paris-Saclay et Univ. Turku, Finlande)

Considérons un ensemble fini de couleurs. Un sous-shift de dimension \(d\) est un ensemble de coloriages de l’espace discret \(\mathbb{Z}^d\) défini par une famille de motifs interdits.

Étant donné en entrée un ensemble de motifs interdits, une question apparaît naturellement : existe-t-il un coloriage qui satisfait ces contraintes ? Ce problème, appelé « problème du domino », fut montré indécidable par Berger en 1966. Cet exposé présente une variante du problème du domino, que nous appelons le « domino apériodique » : étant donné en entrée un ensemble de motifs interdits, existe-t-il un coloriage apériodique (ie. sans vecteur de périodicité non-nul) qui satisfait ces contraintes ?

Comme le domino classique est indécidable, le domino apériodique l’est aussi. Mais quelle est la position précise du domino apériodique dans les hiérarchies usuelles d’indécidabilité ?

Nous montrons que la réponse dépend de la dimension considérée. Il est co-récursivement énumérable (\(\Pi_1^0\)-complet) sur \(\mathbb{Z}^2\), par [Grandjean, Hellouin, Vanier, 2018], mais nous montrons qu’il est analytique (\(\Sigma_1^1\)-complet) sur \(\mathbb{Z}^d\), pour \(d \ge 4\) sur les SFT, et \(d \ge 3\) pour les sous-shifts sofiques.

Il s’agit d’un saut de complexité inhabituellement large pour des problèmes sur de pavages, et à ma connaissance, l’une des premières séparations entre les sous-shifts de dimension deux et les sous-shifts de dimension trois ou quatre.

(Travaux en collaboration avec Benjamin Hellouin de Menibus)