Complexité algorithmique des invariants de type croissance des sous-décalages de type fini sous contrainte dynamique
Silvère Gangloff
I2M, Aix-Marseille Université
Date(s) : 28/06/2018 iCal
14h00 - 16h00
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 innie (Zd,d ≥ 2) dénis par lois locales. Ces objets sont impliqués dans plusieurs domaines des mathématiques et en particulier la physique statistique. Un problème important dans ce cadre est de trouver une formule pour l’entropie. Excepté pour quelques modèles, une telle formule n’est pas connue. De plus, il a été démontré relativement récemment qu’il n’existe pas de méthode pour calculer (algorithmiquement) l’entropie de ces systèmes. Par conséquent, une approche naturelle au problème est de chercher une sous-classe (maximale) sur laquelle il existe un algorithme permettant de calculer uniformément l’entropie.
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ériant 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 (resp. la dimension entropique) peut être calculé uniformément, étendant le domaine dynamique sur lequel un calcul universel peut être implémenté dans les SFT. Le résultat sur le seuil caractérise une classe optimale mais pour les sous-décalage à language décidable, classe un peu plus souple que celle des SFT. Un problème important reste ouvert: celui de trouver une classe optimale 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.
Mots clés : sous-décalages, entropie, invariants topologiques, calculabilité.
Algorithmic complexity of growth-type invariants of SFT under dynamical constraints
Multidimensional subshifts of nite type (SFT) are sets of colorings of an innite regular grid (Zd,d ≥ 2) dened by local rules. These objects are involved in many areas of mathematics and in particular statistical physics. One important problem in this setting is to compute the entropy with a formula. Unfortunately, it was proved, quite recently, that there can not be a general method to compute (algorithmically) the entropy of these systems. The subsequent approach to the problem is to seek for a subclass on which the entropy can be computed algorithmically. That is the main motivation to study the algorithmical complexity of SFT in subclasses dened by dynamical constraints.
In this text, we expose results related to this problem. The most saliant ones are: (1) The existence of aperiodic subshifts of finite type under linear version block gluing constraint, introduced here; (2) a characterization of the values of the entropy for these subshifts (this answers an open question by Hochman and Meyerovitch); (3) a characterization of a threshold on a quantified version of the irreducibility property for the computability of the entropy of decidable subshifts; (4) a characterization of the entropy dimensions of minimal tridimensional SFT. The two characterization results can be interpreted as the approximation from above of some classes of SFT in which the possibility to embed universal computation (and thus have the non-computability of the entropy) vanishes. The result on the threshold characterize an optimal class but is related to decidable subshifts. A challenging open question is to find a similar result for multidimensional SFT. Moreover, we extend this investigation on the unit interval and characterize the values of the entropy of computable interval maps.
Directeurs de thèse
Mathieu Sablik et Guillaume Theyssier
Lien: theses.fr
Catégories
