Limitation de la complexité de certains invariants des sous-décalages par contraintes dynamiques et structurelles

par Solène Esnay (Institut de Mathématiques de Toulouse)

vendredi 21 oct. 2022, 14:30 → 17:30 Europe/Paris

Amphithéâtre Laurent Schwartz, bâtiment 1R3 (Institut de Mathématiques de Toulouse)

Étant donnés un ensemble fini de symboles et une liste de règles spécifiant lesquels d'entre eux peuvent apparaître côte à côte, on peut construire un ensemble – possiblement vide – de lignes infinies de symboles dans les deux directions, obéissant à ces règles, appelées configurations. Un ensemble de configurations est appelé un sous-décalage unidimensionnel, et il s'agit de l'objet mathématique au cœur de la dynamique symbolique. La notion de sous-décalage peut être généralisée en indexant les symboles par Z² – ce qui revient à paver le plan infini discret – ou par n'importe quel groupe de type fini. De nombreuses questions peuvent être posées sur les sous-décalages, notamment s'il existe un algorithme capable de déterminer lesquels d'entre eux sont vides à partir de leurs règles ; et pour un sous-décalage non vide, s'il contient beaucoup de configurations, ou certaines particulièrement complexes. Ces questions correspondent à des invariants de conjugaison : le Problème du Domino, l'entropie, l'apériodicité, la complexité arithmétique du langage.

Cette thèse, subdivisée en trois parties essentiellement indépendantes, étudie comment tous ces invariants sont affectés sous différentes conditions, et comment certaines contraintes sur les sous-décalages peuvent causer des changements dans leur comportement.

 

Dans la première partie, nous nous intéressons aux attracteurs topologiques des automates cellulaires, qui sont des sous-décalages, et montrons quelle complexité maximale ils peuvent atteindre dans la hiérarchie arithmétique.

Dans la deuxième partie, nous fixons des restrictions horizontales sur les sous-décalages bidimensionnels, et souhaitons savoir si le Problème du Domino reste indécidable et quelles sont les entropies possibles pour leurs sous-systèmes de type fini.

 

Dans la troisième partie, nous étendons la définition de sous-décalage aux groupes de type fini, et présentons trois méthodes de constructions distinctes sur les groupes de Baumslag-Solitar, montrant que leur notion d'apériodicité est plus fine que celle qui existe en deux dimensions.