Calculabilité et combinatoire en dynamique symbolique sur des groupes. – CoCoGro

Il peut sembler naturel de se demander si un jeu de tuiles géométriques permet ou non de paver le plan. Par ordre de complexité croissant, on peut en fait se demander 1) si le jeu de tuiles peut paver entièrement le plan ; 2) s’il le peut d’une manière périodique ; et 3) combien de pavages différents existent. Ces trois problèmes, formulés avec une vision combinatoire des pavages, les tuiles de Wang, sont réputés d’une grande difficulté. Aussi appelés sous-décalages de type fini (SFT), ces pavages sont des ensembles de coloriages de la grille infinie qui respectent un nombre fini de contraintes locales. Ils peuvent être vu de manière fructueuse à la fois comme un modèle de calcul (ils peuvent coder des calculs par machine de Turing), mais aussi comme un modèle discret pour les systèmes dynamiques (point de vue de la dynamique symbolique). Ce modèle a déjà été adapté au plan hyperbolique et aux arbres, mais on peut le généraliser : si la grille infinie est vue comme le groupe Z^2, on peut le remplacer par n’importe quel groupe de type fini. Ce nouveau point de vue présente deux avantages : il permet d’unifier les exemples précédents et conduit à des résultats qui ne sont pas spécifiques à un groupe donné ; il définit un modèle de calcul original et qui mérite d’être exploré, les sous-décalages sur des groupes. Pour les informaticiens, les notions mathématiques provenant de la théorie des groupes fournissent une compréhension nouvelle et approfondie des sous-décalages comme modèles de calcul. Pour les mathématiciens, cette approche inspirée de l’informatique propose un point de vue innovant et fertile sur les groupes qui permettra, par exemple, d’exhiber de nouveaux invariants. Tout ceci illustre parfaitement comment les mathématiques et l’informatique théorique peuvent et doivent profiter mutuellement de leurs outils et points de vue respectifs.

Ce projet s’articule autour des trois problèmes susmentionnés, et explore quelles propriétés du groupe contrôlent les propriétés du sous-décalage qu’il définit. La question de l’existence d’un coloriage valide (problème du vide) pour les SFT est décidable sur Z, alors qu’elle est indécidable sur Z^2. Mais peut-on caractériser les groupes qui ont un problème du vide décidable ? La deuxième question concerne les sous-décalages apériodiques, pour lesquels aucun coloriage n’est invariant par translation. Z^2, contrairement à Z, admet des SFT apériodiques. Sur quels groupes en général les SFT peuvent-ils forcer l’apériodicité ? La troisième question concerne l’entropie, qui mesure le taux de croissance des motifs de taille N apparaissant dans un sous-décalage. Calculer cette entropie est aisé pour les SFT sur Z, mais la fonction d’entropie est non calculable sur Z^2. Même si l’on cherche à se concentrer des exemples particuliers de SFTs, calculer l’entropie reste une tâche difficile. Peut-on calculer la valeur exacte de l’entropie pour de nouveaux exemples de SFT en 2D, et trouver de bonnes approximations de l’entropie sur les SFT de Z^2 ?

Depuis une dizaine d’années, l’utilisation des outils de calculabilité, et plus précisément des sous-décalages comme modèles de calcul, a fait preuve d’une grande efficacité en permettant de résoudre d’anciens problèmes en dynamique symbolique. Plus récemment, la communauté internationale, qui se concentrait traditionnellement sur les cas de Z et Z^2 a commencé à s’intéresser au cas des groupes de type fini, qui a permis d’unifier les exemples précédents. L’écriture de ce projet fait suite à l’obtention de plusieurs résultats récents, auxquels les membres du projets ont activement participé. Trois de ces membres sont spécialistes de dynamique symbolique (Nathalie Aubrun, Michael Rao et Jarkko Kari) et sont reconnus au niveau international pour leur expertise sur les questions de calculabilité, de combinatoire des mots et de preuves assistées par ordinateur. Le financement demandé les aidera à renforcer leur position de leadership international.