Projet ANR-14-ACHN-0018 – AutoSim : Auto-similarité en algèbre, dynamique et algorithmique
Programme : Accueil de Chercheurs de Haut Niveau (@RAction) 2014
Année de financement : 2014
Coordinateur du projet : Monsieur Laurent BARTHOLDI (Département de mathématiques et applications de l'ENS)
Partenaires : Laboratoire public
Montant : 550000.0 euros
Durée : 60 mois
Résumé : L'activité de recherches projetée gravite autour d'une idée simple, l'«auto-similarité», et tous ses avatars en géométrie, algèbre, dynamique, et informatique théorique.
Elle argumente fortement en faveur de l'utilisation d'outils provenant de l'algèbre et de l'informatique théorique pour répondre à des questions et mettre en évidence des structures fondamentales sous-jacentes dans des contextes géométriques et dynamiques; et, inversément, d'emprunter des méthodes, idées et constructions de ces domaines pour enrichir des objets algébriques.
L'auto-similarité est un concept puissant : l'idée qu'un objet peut être décrit «récursivement» comme étant construit de copies à échelle réduite de lui-même. Cette auto-référence conduit à des constructions élémentaires d'objets munis de propriétés étonnantes. Un langage commun, celui des «automates à états finis», est mis en avant pour rassembler ces domaines et leur fournir des outils systématiques et unificateurs grâce auxquels leurs problématiques fondamentales peuvent être approchées.
Bien que l'auto-similarité en géométrie et en physique ait été étudiée depuis longtemps, son développement en algèbre est nouveau. La théorie géométrique des groupes fournit des liens entre les intuitions géométriques et algébriques.  Là, l'auto-similarité est interprétée comme le concept d'un groupe contenant des copies, permutées, de lui-même comme sous-groupes. Elle a déjà servi à prouver l'existence de groupes de croissance intermédiaire (répondant à une célèbre question de Milnor), de croissance exponentielle non-uniforme (répondant à une autre question célèbre de Gromov), avec des propriétés spectrales spectaculaires (résolvant une conjecture attribuée à Atiyah), ...
Toutefois, ce n'est qu'un début ! En étendant la notion de groupe auto-similaire, et son interprétation via des automates à états finis, on obtient une plus grande classe de groupes, qui répondra à plus de questions fondamentales en théorie des groupes.
Encore plus récemment, des liens forts sont apparus entre les théories des systèmes dynamiques et des groupes auto-similaires. Ces liens n'ont de loin pas été suffisamment exploités; ils donnent des invariants puissants pour décrire des systèmes dynamiques, et des moyens de les reconstruire ab initio à partir de données algébriques.
Ce projet met en avant l'utilisation de la théorie des groupes, et en particulier des groupes auto-similaires et des automates, pour explorer les systèmes dynamiques, les décomposer canoniquement en pièces élémentaires, les recombiner, et, surtout, fournir un point de vue global, basé sur les automates, de l'espace des paramèmetres de familles entières de systèmes dynamiques.
Toutes ces questions soulèvent des problèmes fondamentaux de complexité : un tel objet est-il calculable ? Comment doit-il être décrit ? La description est-elle efficace ? Il est toujours problématique d'effectuer des calculs finis sur des objets infinis. Les automates à états finis sont des machines particulièrement simples, mais sont assez puissantes pour encoder des groupes et des systèmes dynamiques compliqués.
Les algorithmes conçus pour résoudre ces tâches, de plus, sont d'une grande utilité pratique pour expérimenter avec de nouveaux objets. Ce va-et-vient entre simulation et expérimentation par ordinateur, développement logiciel et recherche purement théorique bénéficie, en fin de compte, aux trois.