[ Combinatoire ] [ Arithmétique ] [ Dynamique ] [ Perspectives ]

Institut de Mathématiques de Luminy


Dynamique, Arithmétique et Combinatoire
Rapport scientifique 1999-2002

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.

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, intitulé "Substitutions in dynamics, arithmetics and combinatorics" est paru en octobre 2002 aux Lecture Notes in Mathematics de Springer-Verlag sous le numéro 1794).

Combinatoire

Combinatoire des mots.

Pour un mot fini ou infini sur un alphabet fini, la fonction de complexité p(n) compte le nombre de facteurs de longueur n.

J. Cassaigne a developpé des techniques pour calculer la fonction de complexité de certaines familles de mots infinis, notamment ceux définis par des substitutions, ainsi que pour construire des mots infinis ayant (au moins asymptotiquement) une fonction de complexité spécifiée. Il a obtenu ainsi des mots dont la complexité n’est ni polynomiale, ni exponentielle.

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. A. Aberkane et S. Brlek (Montréal) ont caractérisé les mots infinis qui ont la même complexité que le mot de Thue-Morse.

J. Cassaigne travaille avec M. Anisiu (Cluj-Napoca) sur la complexité des mots finis et la construction de mots finis de complexité maximale. Il s’intéresse aussi à 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.

J. Cassaigne, S. Ferenczi et C. Mauduit ont étudié, en collaboration avec A. Sárközy (Budapest) la complexité de la fonction de Liouville. Chowla a conjecturé en 1965 que p(n) = 2n mais on ne sait toujours pas démontrer que p(n)n -> +. En deux articles, ils ont démontré d’une part que la conjecture de Chowla est une conséquence de l’hypothèse (H) de Schinzel, et d’autre part que la complexité de la fonction de Liouville tronquée à k nombres premiers est de l’ordre de nk. Ils ont également obtenu de nouvelles estimations concernant les corrélations multiples de la fonction de Liouville.

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

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

B. Adamczewski étudie une classe de suites symboliques, les codages binaires de rotations, intervenant dans des problèmes de répartition des suites (na) 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 qui sont substitutifs.

Mots bidimensionnels.

La fonction de complexité rectangulaire P(m,n) compte le nombre de facteurs rectangulaires de taille (m,n). La conjecture de Nivat dit 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 J. Cassaigne.

Les suites doubles obtenues en codant des plans discrets généralisent les suites sturmiennes : elles 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. Ces suites codent une action de Z2 sur le cercle unité par deux rotations irrationnelles, et ont une complexité P(m,n) = mn + m + n. Ce résultat est dû à V. Berthé, P. Arnoux et S. Ito (Tsuda).

La notion de substitution considérée ci-dessus généralise la notion de substitution de longueur non constante : on associe ainsi aux lettres de l’alphabet des motifs non forcément carrés ou rectangulaires. 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 P. Arnoux et S. Ito (Tsuda) d’une part, et V. Canterini et A. Siegel, d’autre part. V. Berthé et P. Arnoux ont montré que les substitutions multidimensionnelles introduites sont duales des substitutions unidimensionnelles engendrant les fractals de Rauzy généralisés.

V. Berthé et L. Vuillon (Paris 7) montrent que les suites doubles uniformément récurrentes et de complexité mn + n peuvent être considérées comme une généralisation bidimensionnelle des suites sturmiennes. Elles sont en effet toutes obtenues par une projection littérale de suites doubles codant l’approximation d’un plan, ou par le codage d’une action de Z2 sur le cercle unité par deux rotations irrationnelles. En outre, ces suites présentent des propriétés de symétrie généralisant la notion de palindromie unidimensionnelle : on obtient ainsi une caractérisation de ces suites, inspirée par la caractérisation des suites sturmiennes par palindromes.

La notion de C-équilibre s’étend de manière naturelle aux suites doubles en considérant les facteurs rectangulaires de même taille. V. Berthé et R. Tijdeman (Leiden) montrent que, contrairement à ce qui se passe dans le cas unidimensionnel, les suites doubles 1-équilibrées sont totalement périodiques. Ils montrent de plus qu’un codage de rotation d’angle a par rapport à une partition de la forme {[0,ß[,[ß,1[} (avec 1,a ,ß rationnellement indépendants) n’est jamais C-équilibré, quelle que soit la constante C.

P. Hubert et L. Vuillon ont commencé à étudier les mots infinis obtenus comme suites de coupure dans les pavages du plan définis par des polyominos.

Groupes de tresses.

S. 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.

Suites pseudo-aléatoires.

Depuis une soixantaine d’années, de nombreux travaux ont été publiés concernant les suites pseudo-aléatoires. Ils présentent un large éventail d’approches, de techniques et d’applications possibles. La notion même de suite pseudo-aléatoire y est interprétée de bien des manières différentes qui dépendent souvent des applications visées.

La majorité de ces travaux proposent des constructions et/ou des tests de suites pseudo-aléatoires. D’autres travaux utilisent des méthodes issues de la logique mathématique et de la théorie des probabilités pour essayer de mieux analyser et comprendre le concept même de suite pseudo-aléatoire ; mais leur utilité pratique dans la construction effective de telles suites reste alors souvent limitée.

Dans une série de travaux, C. Mauduit et A. Sárközy (Budapest) (certains articles étant en collaboration avec J. Cassaigne, S. Ferenczi et J. Rivat (Nancy)), proposent de donner un cadre théorique précis à la construction de suites pseudo-aléatoires finies ou infinies (11 articles publiés depuis 1999). 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 à 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 (Schlumberger, Louveciennes)).

Arithmétique

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

En collaboration avec C. Dartyge (Nancy), P. Erdös (Budapest), E. Fouvry (Orsay), S. Konyagin (Moscou), C. Pomerance (Bell Labs - Lucent Technologies, Murray Hill), J. Rivat (Nancy) et A. Sárközy (Budapest), C. 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 (6 articles publiés depuis 1999). 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]).

Discrépance.

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

H. Faure et H. 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 ; 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, H. Faure a abordé en 1999 la construction de nouvelles suites à faible discrépance en perturbant aléatoirement des suites déjà connues ; 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, deux articles publiés, un rapport interne d’IBM).

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écisement, le problème posé est le suivant : étant donné un nombre x défini "formellement" (comme p 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. C. Faivre travaille dans cette direction (il a en particulier une borne explicite pour le problème posé ci-dessus), et sur les propriétés ergodiques des quotients partiels du développement en fraction continue.

b -numération.

V. Berthé et A. Siegel étendent l’étude de la représentation p-adique des systèmes substitutifs aux b -shifts et en déduisent une caractérisation des réels ayant un b -développement purement périodique dans le cas Pisot. Ce resultat généralise au cas non unitaire les travaux de Akiyama, Rao et Ito.

Bases additives.

Une base additive asymptotique exacte d’ordre h est un ensemble d’entiers tel que tout entier suffisamment grand s’écrit comme somme de h éléments de la base. J. Cassaigne et A. Plagne (École Polytechnique) étudient la façon dont varie l’ordre d’une base lorsqu’on la prive de l’un de ses éléments. Ils ont montré que la fonction S de Grekos, qui caractérise ce comportement, a une croissance linéaire comprise entre h + 1 et 2h.

Fractions continues généralisées.

On peut décrire parfaitement la combinatoire des suites sturmiennes à l’aide du développement en fraction continue usuel. Par exemple, J. Cassaigne a utilisé ce point de vue pour étudier le spectre des valeurs obtenues comme quotients de récurrence des suites sturmiennes. V. Berthé, C. Holton (Austin) et L. Zamboni étudient les puissances qui apparaissent comme préfixes de suites sturmiennes de même angle en relation avec la numération d’Ostrowski.

La connexion est rendue explicite à travers la description des suites sturmiennes comme limite d’une composition d’un nombre fini de substitutions, où le développement en fraction continue décrit l’itération des substitutions qui interviennent. Une telle représentation (représentation S-adique) existe plus généralement pour les suites de complexité 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ée. Un des intérêts de la représentation S-adique est qu’elle permet une description arithmétique des suites étudiées.

Au-delà du cas sturmien, on connaît explicitement un développement S-adique pour les suites sturmiennes, pour les systèmes engendrés par les codages binaires de rotations (B. Adamczewski), pour les suites telle que lim p(n)n = 1 (A. Aberkane) ou pour les systèmes engendrés par certains échanges de trois intervalles (S. Ferenczi, C. Holton, L. Zamboni).

S. Troubetzkoy et H. Bruin (Groningen) ont obtenu un développement S-adique pour un codage d’une famille de translations par morceaux, ce qui a permis à J. Cassaigne d’en calculer la fonction de complexité.

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. Dans cette étude menée par V. Berthé, P. Arnoux et S. Ito, il ne semble pas que l’algorithme de Jacobi-Perron joue un rôle privilégié. On peut obtenir un résultat similaire avec l’algorithme de Brun. L’algorithme de Brun possède une extension naturelle, dont ils donnent une interprétation géométrique dans ce contexte, afin d’engendrer des fractals de Rauzy pour des paramètres non algébriques. Ceci permet en particulier de donner des exemples de sous-ensembles de tores Td aux propriétés de répartition intéressantes pour les rotations torales (ensembles à restes bornés non triviaux, par exemple).

Les travaux de S. 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, ils généralisent l’interaction rotations / suites sturmiennes, et donnent 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é.

P. Arnoux et P. Hubert ont construit un algorithme de fractions continues généralisées lié au billard octogonal. Un travail en cours de P. Arnoux et T. Schmidt (Oregon) é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.

A. 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, en liaison avec l’étude des propriétés métriques et ergodiques des échanges d’intervalles et feuilletages mesurés.

Dynamique

Dynamique topologique.

S. Ruette et F. Blanchard, avec B. Host (Marne la Vallée), 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.

F. Blanchard, E. Glasner (Tel Aviv), S. Kolyada (Kiev) et A. Maass (Santiago) 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.

F. Blanchard, F. Durand (Amiens) et A. Maass ont obtenu des exemples de systèmes ayant très peu de couples Li-Yorke, en particulier des substitutions de longueur constante.

S. Ruette s’est intéressée à la classification des chaînes de Markov topologiques. Elle a montré qu’un graphe transient peut être inclus dans un graphe récurrent de même entropie ; de plus, si l’entropie de la chaîne de Markov sur le graphe G est strictement supérieure à son entropie locale alors G est positif récurrent.

J. 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.

P. Hubert a étudié la dynamique des translations d’intervalles avec J. Buzzi (École Polytechnique). P. Arnoux poursuit une collaboration à long terme avec A. Fisher (Sao Paulo) sur une généralisation de la dynamique classique : au lieu de considérer l’action des puissances d’une transformation fixée, ils considèrent l’action d’une suite de transformations. Ils montrent ensuite que, dans un tel cadre, l’hyperbolicité et la propriété d’Anosov ont toujours un sens, et ils étudient le cas particulier des suites d’endomorphismes positifs du tore, qui est directement relié au développement en fraction continue usuel.

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

S. 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. Elle a également donné, avec J. Buzzi, une condition suffisante pour qu’une transformation Cr de l’intervalle ait une mesure d’entropie maximale.

L’étude des temps de retour 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, S. Troubetzkoy, avec H. Bruin, B. Saussol (Amiens) et S. Vaienti (Toulon), a developpé 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ù interviennent les temps de retour.

Dans le cas des 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. X. Bressaud s’est intéressé récemment à ce type de systèmes de deux manières. D’une part, il a calculé, avec R. Zweimuller (Penn State), la loi limite des 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, il a construit 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, X. Bressaud a développé avec C. Liverani (Rome) une approche de l’étude des propriétés statistiques des difféomorphismes d’Anosov utilisant une technique de couplage.

Échanges d’intervalles.

S. Ferenczi, C. Holton et L. Zamboni, grâce à une construction explicite des échanges de trois intervalles par trois tours de Rokhlin, déterminent les valeurs propres de l’opérateur spectral associé à la transformation, répondant positivement à deux questions laissées ouvertes par Veech : un échange de trois intervalles non trivial peut avoir des valeurs propres irrationnelles, et peut avoir un spectre discret.

Ils identifient complètement la classe des échanges de trois intervalles qui possèdent la propriété des autocouplages minimaux et trouvent les premiers exemples "naturels" de systèmes simples rigides, fournissant une première réponse partielle positive à une conjecture de Veech sur la propriété de simplicité.

Billards.

Durant les quatre dernières années, P. Hubert a poursuivi sa collaboration avec T. Schmidt sur les groupes de Veech ; ces groupes sont des invariants des surfaces de translation et donc des billards polygonaux, on peut aussi les définir comme les stabilisateurs des disques de Teichmüller sous l’action du mapping class group. Trois articles sont publiés sur ce sujet (l’un d’eux en collaboration avec E. Gutkin). P. Hubert et T. Schmidt ont montré récemment qu’il existe des groupes de Veech qui ne sont pas finiment engendrés, résolvant ainsi une importante question de Veech. 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 la complexité p(n) du langage engendré par le billard. P. Hubert, J. Cassaigne et S. Troubetzkoy ont découvert un lien entre les deux (p(n) = jnN(j)) et ils ont calculé l’ordre asymptotique de croissance de p(n) dans des cas particuliers.

S. Troubetzkoy avec J. Schmeling (Lund) a montré un nouveau théorème sur la dimension de l’ensemble des nombres qui sont bien approximables et en a donné une application aux billards polygonaux.

N. Bedaride s’intéresse au billard dans les polyèdres. Une manière d’étudier l’orbite d’un point dans une direction donnée est de chercher la complexité de la suite symbolique associée. Il a obtenu cette complexité dans le cas des prismes droits à base de polygones pavants. Cette preuve permet de retrouver la complexité dans le cas du cube codé par trois lettres, résultat d’Arnoux, Mauduit, Shiokawa, Tamura.

Systèmes substitutifs.

V. Canterini et A. 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.

A. 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. On obtient ainsi des conditions nécessaires ou suffisantes de connexité des fractals de Rauzy.

Dans le cas où on a bien un pavage, A. 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, A. 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. Le fractal de Rauzy p-adique généralise le cas unimodulaire dans la mesure où il est de mesure non nulle, autosimilaire, et, si la propriété de coïncidence est vérifiée, il existe un échange de morceaux sur cet ensemble qui est mesurablement isomorphe au système substitutif. De plus, on caractérise en recherchant les ambiguïtés du système de numération les systèmes substitutifs de type Pisot non unimodulaire dont le spectre est discret.

P. Arnoux a défini, avec S. Ito et Y. Sano (Tsuda), 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.

Automates Cellulaires.

V. 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. 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é croît avec le nombre de diviseurs premiers distincts de l’entier modulo lequel on réduit.

S. Burckel a construit 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 deux balayages sont nécessaires et conjecture qu’ils suffisent toujours.

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

F. Blanchard, J. Cervelle et E. Formenti ont poursuivi l’étude comparée de la topologie usuelle et des pseudométriques shift-invariantes. Parmi les résultats, il est montré qu’il n’y a pas d’automate transitif pour la topologie de Besicovitch.

Perspectives

Généralisations des développements en fractions continues.

Ce thème fondamental est un excellent exemple des interactions qui font l’originalité de notre équipe ; la situation "classique", à savoir la triple interaction entre les rotations, les suites sturmiennes et les fractions continues usuelles, sert de base à de nombreuses généralisations. Celles-ci permettent de simplifier un certain nombre de faits déjà connus (en particulier, on s’aperçoit que beaucoup d’études arithmétiques ou dynamiques ont un pendant symbolique) et d’autre part d’attaquer divers problèmes ouverts (par exemple, la notion de fractal de Rauzy permet, en utilisant la dynamique symbolique, d’étudier des problèmes qui ne sont pas directement accessibles d’un point de vue purement arithmétique ou géométrique). De manière générale, les algorithmes de fractions continues admettent des interprétations géométriques (en particulier, approximations de droites ou de plans dans des espaces bien choisis, ou clôture convexe des points positifs d’un réseau, appelée polyèdre de Klein), des interprétations dynamiques, comme induction et renormalisation sur une famille paramétrée de systèmes dynamiques, et des interprétations symboliques, comme suites de substitutions ou de substitutions généralisées.

Nous mentionnerons en particulier les problèmes précis suivants :

Autour de la complexité des suites.

Ce thème interagit avec le précédent, les interprétations symboliques des algorithmes de fractions continues faisant intervenir la notion de complexité ; mais il donne aussi naissance à une problématique propre, en liaison avec des questions d’informatique théorique.

Autour des billards.

Ce thème interagit avec les deux précédents en raison des liens des billards avec les échanges d’intervalles et du rôle de la complexité comme invariant.

Suites pseudo-aléatoires et cryptologie.

Les suites pseudo-aléatoires constituent un programme assez vaste sur lequel nous souhaitons mettre en place un groupe de travail transdisciplinaire, car les problèmes posés et les domaines de compétence invoqués sont nombreux (systèmes dynamiques, probabilités, théorie des nombres, combinatoire, logique mathématique, cryptographie, informatique et simulation numérique). Nous avons obtenu en 2000 du Ministère de la Recherche une Action Concertée Incitative en Cryptologie, regroupant J. Cassaigne, C. Mauduit, G. Tenenbaum et J. Rivat (Nancy), coordonnée par J. Rivat ; nous souhaiterions accueillir ce dernier au sein de notre laboratoire afin de nous aider à développer nos projets en interaction avec l’ensemble des équipes.

Quelques autres thèmes.

Les questions qui suivent ne sont pas non plus isolées, dans la mesure où elles ouvrent la voie à des collaborations extérieures à l’équipe.

- Szemerédi-Furstenberg en topologique : dans quels systèmes trouve-t-on des occurrences d’un ouvert en progressions arithmétiques de longueur arbitraire ? (F. Blanchard)

- Étude des propriétés arithmétiques des suite définies par des algorithmes simples (C. Mauduit avec E. Fouvry).

- Étude fine des irrégularités de distribution de suites numériques uni-dimensionelles, les (0,1)-suites de Niederreiter, (H. Faure en relation avec les travaux en cours de Larcher et Pillichshammer).

- Accéleration des méthodes de Monte Carlo par la "derandomization" de suites quasi-aléatoires classiques, les (t,s)-suites de Niederreiter, avec application aux mathématiques financières (H. Faure avec Shu Tezuka, IBM Tokyo Research Laboratory).

Page d'accueil
Sommaire