Calculer l’entropie des sous-décalages mélangeants

Lundi 25 mars 10:15-11:45 - Benjamin Hellouin de Menibus - LRI, Orsay

Résumé : Les sous-décalages multidimensionnels sont des sous-ensembles des coloriages de la grille Z^d par un alphabet fini A, invariants par toutes les translations. L’entropie d’un sous-décalage est le taux de croissance exponentiel du nombre de coloriages admissibles dans la boule de diamètre n, et est une notion naturelle pour diverses communautés : théorie de l’information, combinatoire, systèmes dynamiques, physique statistique.
Quand le sous-décalage est défini par un nombre fini de contraintes (cas de « type fini ») en dimension 1, une méthode algébrique classique résout le problème complètement. Le cas général (dimension >1) s’est révélé beaucoup plus difficile et l’entropie de certains exemples simples reste à déterminer. En 2007, il a été montré que l’entropie est incalculable en général ; cependant, des travaux récents montrent que des hypothèses de mélange fort suffisent à rendre le problème traitable. Où se situe la limite entre les cas calculables et incalculables ?
Après un exposé historique de l’état de l’art, j’introduirai une notion de taux de mélange qui fait « sauter » l’entropie de calculable à incalculable à un certain seuil. Nous déterminons la position de ce seuil pour une famille un peu plus générale (nombre de contraintes infini), et conjecturons un résultat similaire pour le cas de type fini.
Cet exposé n’utilise que des notions basiques de calculabilité, qui seront introduites ; aucun pré-requis n’est nécessaire.

Lieu : salle 3L8

Calculer l’entropie des sous-décalages mélangeants  Version PDF