Auto-similarité en algèbre, dynamique et algorithmique – AutoSim

Un langage commun, celui des \emph{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), \dots

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 \emph{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.

Already three articles written, 2 accepted

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.