Etienne Moutot (LIP, ENS Lyon)

A quel point peut-on créer des structures complexes à l’aide de motifs élémentaires ? La conjecture de Nivat dit que toute configuration (coloration de la grille Z^2) de faible complexité (le nombre de motifs qui y apparaissent est “faible”) est nécessairement périodique. Autrement dit, il est impossible des créer des configuration “complexes” (non périodiques) à l’aide d’un petit nombre de motifs de base.

En 2015, Michal Szabados et Jarkko Kari ont publié leur premier article utilisant une approche algébrique pour s’attaquer à cette conjecture. Leur idée est de représenter une configuration comme une série formelle, et en étudiant certaines structures qui lui sont liées (tels que des idéaux polynomiaux bien choisis). Ce faisant, ils parviennent à exploiter plusieurs théorèmes d’algèbre pour s’approcher de la conjecture de Nivat sous des angles nouveaux.

Dans cet exposé, je présenterai les travaux que j’ai effectué avec Jarkko Kari dans le continuation de la thèse de Michal Szabados. Je parlerai de nouveaux théorèmes utilisant ces outils algébriques pour se rapprocher encore une fois de la conjecture de Nivat. Une des conséquences de ces résultats est que le problème du domino est décidable pour les sous-shifts de faible complexité. Ce problème est indécidable de manière générale, et si la conjecture de Nivat est vraie, il serait décidable de manière évidente. Un des intérêt de notre résultat est qu’il permet de prouver cette décidabilité, sans pour autant avoir besoin de la conjecture de Nivat, seulement une version affaiblie.

Clement Julien Last modified: Mon Sep 30 16:34:16 CEST 2019