Algorithmic complexity of growth-type invariants of SFT under dynamical constraints
Silvère Gangloff · 2018
Complexité algorithmique des invariants de type croissance des sous-décalages de type fini sous contrainte dynamique Les sous-décalages multidimensionnels (SFT) sont des ensembles de colorations d'une grille régulière infinie définis par lois locales. Ces objets sont impliqués dans plusieurs domaines des mathématiques et en particulier la physique statistique. Un problème important est de calculer leur entropie. Cependant, il a été prouvé qu'il n'existe pas d'algorithme uniforme pour faire ce calcul. Une approche naturelle est de trouver une classe de SFT, définie par des contraintes dynamiques, sur laquelle ceci est vrai. Dans ce texte, on propose des résultats reliés à ce problème. Les plus important d'entre eux sont: (1) l'existence de SFT apériodiques vérifiant une variante de la propriété d'assemblage introduite ici et appelée assemblage linéaire; (2) une caractérisation des valeurs de l'entropie pour ces SFT (répondant en particulier à une question ouverte de Hochman et Meyerovitch); (3) une caractérisation d'un seuil pour la calculabilité de l'entropie pour les sous-décalages multidimensionnels à language décidable; (4) une caractérisation des valeurs possibles de la dimension entropique pour les SFT tridimensionnels minimaux. Les deux résultats de caractérisation peuvent être interprétés comme une approximation par le haut de classes de SFT optimales sur lesquelles l'entropie peut être calculé uniformément. Le résultat sur le seuil caractérise une classe optimale mais pour les sous-décalage à langage décidable. Le même problème reste ouvert pour les SFT multidimensionnels. De plus, on étend le problème à l'intervalle unité, et caractérise les valeurs possibles de l'entropie pour les fonctions calculables de l'intervalle.