RESEARCH IN RESIDENCE
Diagrammatical Symbolic Dynamics
Dynamique Symbolique Diagrammatique
11 – 15 November, 2024
Participants
Nicolas Bitar (Université de Picardie Jules-Verne)
Titouan Carette (École polytechnique)
Victor Lutfalla (Aix-Marseille Université)
Etienne Moutot (Aix-Marseille Université)
Renaud Vilmart (Inria Saclay)
Central objects of symbolic dynamics are subshifts, which are sets of (bi-)infinite words defined by a set of forbidden patterns. The definition can also be extended to infinite configurations over ℤ𝑑 or even any finitely generated group. When the set of forbidden patterns is finite, the subshift is said to be of finite type, and is then conjugate to a set of tilings of the space by Wang tiles.
Recently, Titouan Carette and Etienne Moutot defined a generalization of Wang tiles based on tensor networks, and largely inspired by graphical languages used to describe quantum computation, such as ZX calculus. Applied to the particular tilings by dimers, Titouan Carette, Etienne Moutot, Thomas Perez and Renaud Vilmart have drawn strong links between counting dimer tilings (or equivalently perfect matchings of graphs) and the graphical language called ZW calculus, allowing to count perfect matching with techniques based only on diagram rewriting.
However, the graphical languages described above are only able to describe finite patterns of tilings, or finite pattern extracted from subshifts of finite type. The next step is logically to improve it in order to be able to talk about infinite configurations of ℤ or ℤ𝑑 and then have a graphical language capable of describing entire subshifts. Last Summer, Titouan Carette and Vivien Ducros (in Masters internship) successfully drafted a diagrammatic formalism which is
able to define one dimensional sofic subshifts and subshifts of finite type using diagrams on relations.
The objective of this research in residence is to continue to extend and explore this diagrammatic formalism. More precisely, our goal is to extend the formalism to subshifts of higher dimension, and even on finitely generated groups. We also want to be able to capture other type of subshifts using diagrams, such as effective of substitutive shifts. Our hope is that this diagrammatic formalism will allow us to generalize in a natural ways many tools that are used in one-dimensional symbolic dynamics to higher dimensions. One field of application may be to provide new tools to better understand pattern complexity and entropy in dimension two and above.
Les objets centraux de la dynamique symbolique sont les sous-shifts, qui sont des ensembles de mots (bi-)infinis définis par un ensemble de motifs interdits. La définition peut être étendue à des configurations en dimension quelconque (sur ℤ𝑑) ou sur des groupes de type fini. Quand l’ensemble de motifs interdit est fini, on parle de sous-shift de type fini (SFT), et il est alors conjugué à un ensemble de pavages par tuiles de Wang.
Récemment, Titouan Carette et Etienne Moutot ont proposé une généralisation des tuiles de Wang basées sur les réseaux de tenseurs, largement inspirée par les langages graphiques utilisés en informatique quantique, tels que le ZX calcul ou le ZW calcul. Dans le cas particulier des pavages par dimères, Titouan Carette, Etienne Moutot, Thomas Perez et Renaud Vilmart ont montré qu’il existait des liens forts entre le comptage de dimères (ou de manière équivalente de couplages parfaits dans des graphes) et le langage graphique du ZW calcul. Ceci a permis de développer des nouvelles techniques de comptages de couplages parfaits basées uniquement sur la ré-écriture de diagrammes.
Cependant, ce langage graphique ne permet que de traiter du cas de motifs ou de pavages finis. L’étape suivante est donc d’étendre pour pouvoir également décrire des configurations infinies de ℤ ou ℤ𝑑, et pouvoir obtenir un langage graphique capable de décrire des sous-shifts. L’été dernier, Titouan Carette et Vivien Ducros (en stage de Master) ont commencé à dessiner les lignes de ce nouveau formalisme, arrivant à définir diagrammatiquement les sous-shifts sofiques et de type fini en dimension 1.
L’objectif de cette recherche en résidence est de continuer d’étendre et d’explorer ce formalisme diagrammatique appliqué aux sous-shifts. Plus précisément, notre but est de l’étendre aux dimensions supérieurs, ainsi qu’aux groupes de type fini. Nous aimerions aussi être capables de définir d’autres types de sous-shifts, tels que les sous-shifts substitutifs ou effectifs. Notre but est d’utiliser ce formalisme pour généraliser de nombreux outils de dimension 1 qui n’ont pas d’analogue en dimension supérieure. Une application possible serait par exemple le calcul de complexité ou de l’entropie de certains sous-shifts en dimension 2 et supérieure.
SPONSOR
