Around abstract numeration systems

Un système de numération, comme notre système décimal usuel, peut être vu comme une bijection entre l'ensemble des entiers naturels et le langage formé des représentations de ces entiers. Lorsque l'on considère, de façon générale, une numération basée sur une suite strictement croissante d'entiers et pour laquelle les représentations sont obtenues par un algorithme glouton, la bijection qui à un entier associe sa représentation préserve l'ordre naturel. Ainsi, un système de numération abstrait est la donnée d'un langage L infini (le plus souvent régulier) ordonné par ordre généalogique croissant. L'entier n est alors représenté par le n-ième mot du langage L. L'introduction, il y a une dizaine d'années, de ces systèmes abstraits a été motivée par le théorème de Cobham de 1969 qui s'intéresse aux ensembles reconnaissables d'entiers. Un ensemble X d'entiers est dit S-reconnaissable, pour une numération fixée S, si l'ensemble des représentations dans le système S des éléments de X forme un langage régulier. Ainsi les ensembles S-reconnaissables sont, d'un certain point de vue, particulièrement simples puisque décrits par un automate fini. Le théorème de Cobham stipule que les seuls ensembles d'entiers simultanément reconnaissables pour deux bases entières k et l suffisamment indépendantes, à savoir multiplicativement indépendantes, sont exactement les unions finies de progressions arithmétiques. Ce théorème a été le point de départ de nombreux travaux de recherche au cours de ces quarante dernières années (généralisations à des numérations non standards, à plusieurs dimensions, formalisme logique,... ). Dans ce survol liant théorie élémentaire des nombres et théorie des automates, nous nous proposons de présenter quelques questions et développements en lien directe avec cette question générale : existe-t-il un lien entre les propriétés arithmétiques des nombres (e.g., carré parfait, nombre premier, critère de divisibilité, ...) et les propriétés syntaxiques de leurs représentations ? Les propriétés décrites par automates finis sont-elles, par exemple, stables en appliquant des opérations arithmétiques élémentaires comme l'addition ou la multiplication par une constante ? Les automates permettent également de tracer des liens avec la combinatoire des mots (suites automatiques au sens d'Allouche et Shallit et plus généralement mots morphiques engendrés par substitution) ou d'exprimer certains problèmes de décision dont la solution revient à étudier la complexité en nombre d'états (state complexity) de certaines familles de langages