Institut de Mathématiques de Luminy

Équipe
Dynamique, Arithmétique et Combinatoire


Introduction :
Le choix de la subdivision en thèmes et sous-thèmes adoptée est très arbitraire. Une des spécificités de l'équipe est justement la variété des interactions entre différents domaines.
Seul le travail sur les applications à la génomique distingue réellement une partie peu nombreuse mais dynamique de l'équipe.
Il faut signaler que plusieurs membres de l'équipe sont éditeurs d'un ouvrage collectif de 400 pages qui donne un survol des substitutions et des questions reliées, abordant une grande partie des thèmes de l'équipe ; une version préliminaire a déjà connu une assez large diffusion, et rencontré un grand succès (cet ouvrage est soumis aux Lecture Notes in Mathematics de Springer-Verlag).

1 - Génome
2 - Combinatoire
3 - Arithmétique
4 - Dynamique


2.1. Génome.

2.1.1. Structure du génome.

Brigitte Mossé collabore avec des biologistes pour développer des outils pour l'analyse des séquences génétiques (structure secondaire, complexité), et la comparaison de ces séquences (alignement).

Les recherches d'Alain Guénoche dans ce domaine portent sur l'étude des distances d'arbre, en rapport avec les questions de reconstruction phylogénétique. Il a défini des méthodes de reconstruction à partir de distances partielles et étudié la complexité du prolongement d'une distance partielle en une distance d'arbre.

2.1.2. Puces à ADN.

Alain Guénoche a aussi travaillé sur la conception des puces à ADN et l'analyse des données qu'elles fournissent (classification suivant les intensités d'hybridation de sondes).

2.2. Combinatoire.

2.2.1. Combinatoire des mots.

Les recherches de Brigitte Mossé portent, dans ce domaine, sur la combinatoire des langages formels, plus précisément ceux associés à un d0l-système (procédé substitutif).

Pour un mot fini ou infini sur un alphabet fini, la fonction de complexité p(n) compte le nombre de facteurs de longueur n. Julien Cassaigne travaille avec M. Anisiu (Cluj-Napoca) sur la complexité des mots finis et la construction de mots finis de complexité maximale.

Les mots sturmiens peuvent être caractérisés par leur fonction de complexité et on connaît assez peu d'autres exemples pour lesquels cela est possible. Ali Aberkane et S. Brlek (Montréal) ont caractérisé les mots infinis qui ont la même complexité que le mot de Thue-Morse.

Julien Cassaigne s'intéresse à d'autres fonctions associées à des mots infinis, comme la fonction de récurrence ou la fonction de complexité palindromique.

Par exemple, avec J-P. Allouche (Orsay), M. Baake (Greifswald) et D. Damanik (Caltech), ils ont comparé la fonction de complexité palindromique à la fonction de complexité usuelle.

Les suites sturmiennes sont 1-équilibrées. On pensait que les suites d'Arnoux-Rauzy (généralisation des suites sturmiennes à 3 lettres) auraient des propriétés similaires. Julien Cassaigne et Sébastien Ferenczi, avec L. Zamboni (North Texas), ont construit des suites d'Arnoux-Rauzy qui ne sont k-équilibrées pour aucune valeur de k.

Julien Cassaigne travaille avec J. Karhumäki et J. Manuch (Turku) sur les équations sur les langages, notamment la commutation et la conjugaison.

Boris Adamczewski étudie une classe de suites symboliques, les codages binaires de rotations, intervenant dans des problèmes de répartition des suites (n) et représentant une généralisation géométrique des suites sturmiennes. Il montre que ces suites peuvent être obtenues en itérant infiniment quatre substitutions sur un alphabet à quatre lettres, puis en appliquant une projection. Il caractérise ainsi les codages binaires de rotations substitutifs.

2.2.2. Mots bidimensionnels.

La fonction de complexité rectangulaire P(m,n) compte le nombre de facteurs rectangulaires de taille (m,n). On conjecture que s'il existe un couple d'entiers (m,n) tels que P(m,n) mn, alors la suite est périodique. En revanche il existe des suites doubles non périodiques de complexité mn+1 qui ont été caractérisées par Julien Cassaigne.

Les suites doubles obtenues en codant des plans discrets généralisent les suites sturmiennes, tout en produisant des exemples de suites doubles substitutives, où la substitution sous-jacente associe aux lettres des motifs non rectangulaires. Ces suites "sturmiennes'' doubles sont de plus engendrées par des substitutions bidimensionnelles dont l'itération est gouvernée par l'algorithme multidimensionnel de fractions continues de Jacobi-Perron, ce qui généralise le cas sturmien. Ce résultat a été obtenu par Valérie Berthé, Pierre Arnoux et S. Ito. La notion de substitution considérée ici généralise la notion de substitution de longueur non constante.

Après renormalisation, les itérés de ces substitutions généralisées convergent vers un domaine compact à frontière fractale. Dans le cas où les paramètres de départ sont algébriques,

on retrouve les fractals de Rauzy généralisés associés aux systèmes dynamiques substitutifs Pisot et unimodulaires, étudiés par Vincent Canterini et Anne Siegel d'une part, et Pierre Arnoux et S. Ito (Tsuda), d'autre part. Valérie Berthé et Pierre Arnoux ont montré que les substitutions multidimensionnelles introduites sont duales des substitutions unidimensionnelles engendrant les fractals de Rauzy généralisés.

2.2.3. Suites pseudo-aléatoires.

Dans une série de travaux, Christian Mauduit et A. Sarközy (Budapest) (certains articles étant en collaboration avec Julien Cassaigne, Sébastien Ferenczi et J. Rivat (Nancy)), proposent de donner un cadre théorique précis à la construction de suites pseudo-aléatoires finies ou infinies (7 articles publiés en 1999 et 2000). Les mesures qu'ils définissent sont liées à la fois à la normalité, à la répartition dans les progressions arithmétiques et au contrôle des corrélations multiples de ces suites. Elles permettent, par exemple, grâce au recours à des méthodes issues soit de la théorie des systèmes dynamiques, soit de la géométrie algébrique, d'analyser les propriétés statistiques de certaines suites arithmétiques binaires classiques (suites automatiques, symbole de Legendre, fonction de Liouville, codages de produits croisés au-dessus de rotations irrationnelles du tore, ...). Certaines constructions pourraient conduire à des applications intéressantes en cryptographie (travail en collaboration avec L. Goubin (Bull PTS, Louveciennes)).

2.2.4. Groupes de tresses.

Serge Burckel étudie les groupes de tresses et en particulier la structure de leur ordre. Cette approche lui permet de construire des méthodes syntaxiques efficaces pour les tresses positives, notamment pour le problème de mots et le calcul de la fonction de croissance.

Xavier Bressaud s'est intéressé à l'utilisation de méthodes dynamiques "à la Vershik'', pour l'étude de marches aléatoires sur les groupes, et plus particulièrement sur les groupes de tresses. Un objectif est d'obtenir une description combinatoire adaptée du "bord'' de ces groupes.

2.3. Arithmétique.

2.3.1. Propriétés arithmétiques des suites automatiques.

En collaboration avec C. Dartyge (Nancy), P. Erdös (Budapest), S. Konyagin (Moscou) et A. Sarközy (Budapest), Christian Mauduit a développé des méthodes permettant d'étudier les propriétés multiplicatives des suites d'entiers dont le développement q-adique évite certains chiffres (5 articles publiés entre 1999 et 2001). Ceci a permis en particulier de répondre à une question vieille de 30 ans posée par Erdös et d'obtenir un théorème d'Erdös-Kac dans le cas d'ensemble de densité en x – c (c [ 1/2, 1 ]).

2.3.2. Discrépance.

Boris Adamczewski s'intéresse à la distribution de la suite (n) dans l'intervalle [0,[, pour certains couples de paramètres (,) ( quadratique, et Z + Z). Il déduit de cette étude un résultat de répartition à l'origine pour certains paramètres . Ces résultats sont obtenus par une approche symbolique (étude de codages binaires de rotations substitutifs).

Ces deux dernières années, Henri Faure et Henri Chaix ont continué la recherche de bornes inférieures pour la discrépance de suites infinies en dimension 2 ; après l'annonce de résultats partiels, ils ont fait une étude annexe sur les sommes des coefficients binomiaux pour obtenir des estimations plus complètes ; cette étude, intéressante en elle-même, a donné lieu à 2 publications ; actuellement, ils mènent en parallèle la rédaction d'un article détaillé en dimension 2 et la prospection en dimension 3 (en collaboration avec E. Thiémard de l'EPF de Lausanne).

D'autre part, Henri Faure a abordé en 1999 la construction de nouvelles suites à faible discrépance en perturbant aléatoirement des suites déjà connues ; annoncée à Hong-Kong, cette construction a été généralisée (en collaboration avec S. Tezuka, IBM Tokyo) et appliquée avec succès à des problèmes de mathématiques financières (pricing of financial derivatives, article soumis).

2.3.3. Fractions continues classiques.

Un problème pratique important dans la théorie des fractions continues est celui de la détermination explicite du développement. Plus précisément, le problème posé est le suivant : étant donné un nombre x défini "formellement'' (comme par exemple) et un entier k 1, combien faut-il prendre de décimales de x pour en extraire les k premiers quotients partiels ? Les premiers résultats significatifs dans cette direction ont été obtenus par Lochs dans les années 60.

Christian Faivre travaille dans cette direction. Dans un troisième article sur le sujet, il donne une borne explicite pour le problème posé ci-dessus et prouve de nouveaux résultats.

Par ailleurs, il a écrit un article sur les propriétés ergodiques des quotients partiels du développement en fraction continue.

2.3.4. Fractions continues généralisées.

On peut décrire parfaitement la combinatoire des suites sturmiennes (cadre classique ou cadre multidimensionnel) à l'aide du développement en fraction continue usuel. Par exemple, Julien Cassaigne a utilisé ce point de vue pour étudier le spectre des valeurs obtenues comme quotients de récurrence des suites sturmiennes.

La connexion est rendue explicite à travers la description des suites sturmiennes comme limite d'une composition d'un nombre fini de substitutions. Une telle représentation (représentation S-adique) existe plus généralement pour les suites de complexité sous-linéaire. Ce mode d'engendrement algorithmique permet d'associer naturellement à la suite, dans de nombreux cas, un développement en fraction continue généralisé.

On connaît par exemple explicitement un développement S-adique pour les suites sturmiennes, pour les systèmes engendrés par les codages binaires de rotations (Boris Adamczewski), pour les suites telles que limp(n)n = 1 (Ali Aberkane) ou pour les systèmes engendrés par certains échanges de trois intervalles (Sebastien Ferenczi, C. Holton, L. Zamboni).

L'approche S-adique peut s'étendre à un cadre multidimensionnel. On peut engendrer un plan discret par limite de composition de substitutions généralisées, itération gouvernée par l'algorithme de Jacobi-Perron (Valérie Berthé, Pierre Arnoux et S. Ito).

Les travaux (mentionnés ci-dessus) de Sébastien Ferenczi, avec C. Holton et L. Zamboni, portent sur les propriétés combinatoires, arithmétiques et dynamiques des échanges d'intervalles. A l'aide d'un algorithme combinatoire dit "hat algorithm'' et d'un nouvel algorithme de fractions continues pour l'approximation simultanée de deux nombres, on donne un critère nécessaire et suffisant pour qu'une suite symbolique soit un codage naturel d'un échange de trois intervalles. On peut alors construire explicitement les codages des orbites des discontinuités, et, en calculant les mots de retour, obtenir une présentation S-adique du système dynamique associé : on peut alors répondre à des questions de Veech sur les valeurs propres, qui restaient ouvertes depuis longtemps.

Pierre Arnoux et Pascal Hubert ont construit un algorithme de fractions continues généralisées lié au billard octogonal. Un travail en cours de Pierre Arnoux et T. Schmidt étudie les relations entre cet algorithme et celui de Rosen. Plusieurs résultats intermédiaires ont déjà été obtenus, en particulier une construction explicite de l'extension naturelle. Ce domaine, intimement lié à la dynamique des billards, pose aussi de nombreuses questions de théorie algébrique des nombres et de surfaces de Riemann.

Pierre Arnoux avec Arnaldo Nogueira s'intéresse à la Théorie Ergodique des flots sur les espaces homogènes et ses applications à la Théorie des Nombres. Il s'intéresse en particulier aux algorithmes euclidiens. Si ils sont motivés par les approximations diophantiennes, ils apparaissent aussi de manière tout à fait naturelle dans l'étude des propriétés métriques et ergodiques des échanges d'intervalles et feuilletages mesurés.

2.4. Dynamique.

2.4.1. Dynamique topologique.

Sylvie Ruette et François Blanchard, avec B. Host, ont démontré que tout système topologique d'entropie positive contient beaucoup de couples asymptotiques ; quand le système est inversible "presque tous" ces couples sont "instables", ici Li-Yorke, pour la transformation inverse.

François Blanchard, E. Glasner, S. Kolyada et A. Maass ont montré que l'entropie positive entraîne le chaos de Li-Yorke (question ouverte depuis plus de 20 ans), et étudié les propriétés des systèmes sans couples Li-Yorke.

Julien Cassaigne a construit, avec V. Blondel (Louvain) et C. Nichitiu (Saint-Etienne), un contre-exemple à une conjecture de P. Kurka sur la dynamique des machines de Turing : il existe une machine qui n'a aucune configuration périodique.

Pascal Hubert a etudié la dynamique des translations d'intervalles avec J. Buzzi.
Sylvie Ruette a construit pour tout entier r > 1 une transformation Cr de l'intervalle, topologiquement mélangeante, pour laquelle il n'existe pas de mesure d'entropie maximale.

2.4.2. Propriétés statistiques des systèmes dynamiques.

L'étude des temps de retours est un ingrédient important pour la description statistique des systèmes dynamiques. Plusieurs approches ont permis de montrer qu'un grand nombre de systèmes chaotiques ont une statistique exponentielle des temps des retours.

Récemment, Serge Troubetzkoy a développé une nouvelle approche qui a permis de montrer que quelques cas restants ont aussi une statistique exponentielle. Un exemple particulier de cette approche est celui des applications de l'intervalle pour lesquelles les orbites critiques ne sont nulle part denses.

Il a aussi commencé l'étude du formalisme thermodynamique des temps de retours. Dans le cas d'une application, il a montré qu'il y a des formules pour l'exposant de Lyapunov et la dimension locale où intervient les temps de retours.

Dans le cas d'applications dilatantes de l'intervalle, la présence d'un point fixe indifférent peut faire apparaître naturellement des mesures invariantes absolument continues qui ne sont pas finies. Xavier Bressaud s'est intéressé récemment à ce type de systèmes de deux manières.

D'une part en calculant, avec R. Zweimuller, la loi limite de temps de retour dans certaines suites d'évènements asymptotiquement rares. La loi exponentielle apparaissant dans le cadre hyperbolique est remplacée par une loi "heavy tail''.

D'autre part, en construisant une famille d'exemples d'applications dilatantes de l'intervalle pour lesquelles peuvent apparaître plus de deux mesures naturelles, à des échelles de temps différentes.

Par ailleurs, Xavier Bressaud a développé avec C. Liverani une approche de l'étude des propriétés statistiques des difféomorphismes d'Anosov utilisant une technique de couplage.

2.4.3. Billards.

Durant les deux dernières années, Pascal Hubert a poursuivi sa collaboration avec T. Schmidt sur les groupes de Veech (groupes qui sont des invariants des surfaces de translation et donc des billards polygonaux). Deux articles sont écrits sur ce sujet.
Un autre est en cours d'élaboration en collaboration avec E. Gutkin et T. Schmidt. Ces résultats sont à relier aux fractions continues généralisées.

Les billards polygonaux ont une entropie topologique nulle. Pour décrire plus précisément leur comportement, les spécialistes des billards ont étudié deux objets : le nombre N(n) de diagonales généralisées de longueur inférieure à n et le nombre p(n) de mots de longueur n dans la langage engendré par le billard (complexité). Pascal Hubert, Julien Cassaigne et Serge Troubetzkoy sont en train de terminer un article sur ces notions.

2.4.4. Systèmes substitutifs.

Vincent Canterini et Anne Siegel ont explicité une application continue, partant du système symbolique associé à une substitution de type Pisot et à valeurs dans le fractal de Rauzy de cette substitution.

Anne Siegel a montré que les ambiguïtés du système de numération associé à une substitution unimodulaire de type Pisot sont descriptibles par un graphe fini. Ceci permet de caractériser de manière effective les substitutions unimodulaires de type Pisot dont le fractal de Rauzy engendre un pavage périodique autosimilaire.

Dans le cas où on a bien un pavage, Anne Siegel a montré que le fractal de Rauzy d'une substitution permet de définir une partition de Markov pour l'action de la matrice de la substitution dans le tore, dont l'intérêt principal est que ses propriétés géométriques peuvent être étudiées (connexité, simple connexité...).

Grâce à des représentations p-adiques, Anne Siegel a associé à toute substitution de type Pisot non unimodulaire un fractal de Rauzy p-adique, et a caractérisé les systèmes associés qui sont à spectre discret, ainsi que leurs facteurs p-adiques.

Pierre Arnoux a défini, avec S. Ito et Y. Sano, une notion plus générale d'extension des substitutions en toute dimension, ainsi que d'extension duale dans le cas de déterminant 1; cette notion devrait permettre d'étendre une partie des résultats obtenus dans le cas Pisot à un cadre plus général.

2.4.5. Automates Cellulaires.

Valérie Berthé a étudié la complexité rectangulaire de suites doubles engendrées par des automates cellulaires linéaires avec condition initiale polynomiale définis modulo un entier, dans le but de comparer le "désordre'' de ces suites doubles selon ses réductions. En particulier, cette étude s'applique au triangle de Pascal. On obtient alors que la complexité est quadratique si et seulement si l'on réduit modulo une puissance d'un nombre premier ; de plus, la complexité croit avec le nombre de diviseurs premiers distincts de l'entier modulo lequel on réduit.

Serge Burckel a construit ad hoc sur tout ensemble fini une opération de Scheffer définie avec le zéro, le successeur et la comparaison. La preuve est purement combinatoire. Actuellement, son sujet principal concerne un modèle de calcul des transitions du type X := F(X) sur n composantes. Il cherche les moyens de les calculer efficacement de manière séquentielle et interne (en utilisant seulement les n composantes). Il a prouvé que ce type de calcul existe toujours et avec au plus n balayages (assignations successives des composantes). Il montre que 2 balayages sont nécessaires et conjecture qu'ils suffisent toujours.

Xavier Bressaud et Pierre Tisseur, ont construit un exemple d'automate cellulaire sensible aux conditions initiales et d'entropie nulle répondant ainsi partiellement à une question de Wolfram.

Last update : September 22, 2001, EL.