David Madore's WebLog: L'arbre de Stern-Brocot

Index of all entries / Index de toutes les entréesXML (RSS 1.0) • Recent comments / Commentaires récents

Entry #0935 [older|newer] / Entrée #0935 [précédente|suivante]:

(vendredi)

L'arbre de Stern-Brocot

Ce que je trouve fascinant dans les mathématiques, ce sont les objets infiniment élégants qu'on peut y rencontrer : je ne m'enthousiasme pas tant pour les démonstrations que pour les créatures qui peuplent le paradis platonique et dont on a vraiment l'impression qu'elles existent et qu'on ne fait que les découvrir et non les inventer. La créature que j'ai rencontrée en l'occurrence (pas aujourd'hui, mais c'est aujourd'hui que j'ai appris son nom), c'est l'arbre de Stern-Brocot : il se trouve que je l'ai redécouvert (et je suppose que je ne suis pas le premier ; déjà, il porte un double nom en l'honneur de deux personnes — Moris Stern et Achille Brocot — qui l'ont découvert indépendamment) dans ma thèse (voyez page 26 de mon manuscrit) en étudiant la résolution par éclatement des morphismes depuis la droite projective, mais je suppose que j'aurais pu le rencontrer en mille et une circonstances tellement il est naturel. J'en discutais avec un ami (Arthur), qui m'a fait remarquer que cet arbre était déjà connu et signalé dans Concrete Mathematics (le livre de Graham, Knuth et Patashnik), et c'est là que j'en ai appris le nom.

Il s'agit d'un arbre binaire dont les feuilles sont exactement les nombres rationnels (du moins tel que je le conçois, avec zéro pour racine ; d'autres présentations prennent des sous-arbres de ce que j'évoque) : il a pour racine le nombre 0, dont partent deux feuilles étiquetées −1 (à gauche) et 1 (à droite) ; au niveau suivant, les feuilles sont −2 et −½ (filles de la feuille −1), ½ et 2 (filles de la feuille 1) ; au niveau suivant ce sont −3, −3/2, −2/3, −1/3, 1/3, 2/3, 3/2 et 3. À chaque niveau, la règle de construction est de placer entre deux fractions déjà formées la fraction dont le numérateur et le dénominateur sont chacun somme de ceux des deux fractions gauche et droite entre lesquelles on intercale la nouvelle (par exemple, entre 1/2 et 2/3 on mettra 3/5, qui sera fils gauche de 2/3). Peut-être que les explications de PlanetMath ou celles de MathWorld, avec dessin, seront plus claires. Cet arbre contient une et une seule fois chaque rationnel, qui apparaît sous forme réduite, et les irrationnels correspondent à des branches dans l'arbre de Stern-Brocot ; de plus, il a des propriétés miraculeuses liées à l'algorithme d'Euclide (d'écriture des réels en fractions continuées) : si on suit une branche de l'arbre, les fractions qui apparaissent sont exactement les meilleures approximations rationnelles du réel limite, et les changements de direction (de la gauche vers la droite ou vice versa) se font exactement aux réduites de l'écriture du réel en fraction continuée. Par exemple, si on part de 1 et qu'on alterne branche droite et branche gauche, on trouve les rapports successifs des nombres de Fibonacci (2, 3/2, 5/3, 8/5, 13/8…) qui sont les approximants d'Euclide convergeant vers le nombre d'or.

[Graphe de la fonction de Stern-Brocot]Je ne m'arrête pas là : supposons que je mette en correspondance l'arbre de Stern-Brocot (mettons le sous-arbre qui a pour sommet ½, entre 0 et 1) avec l'arbre dyadique de même intervalle (qui a pour sommet ½ dont partent deux branches vers ¼ et ¾ et ensuite vers les huitièmes et ainsi de suite). On obtient une fonction continue croissante (représentée ci-contre) qui à tout rationnel (entre 0 et 1) associe un nombre dyadique (c'est-à-dire un rationnel dont le dénominateur est une puissance de 2) : elle envoie par exemple 1/2 sur 1/2, 1/3 sur 1/4, 2/3 sur 3/4, 3/5 sur 5/8 et 5/8 sur 11/16. Cette fonction se prolonge (de façon unique) en une fonction croissante continue φ de l'intervalle [0;1] sur lui-même, qui fait correspondre exactement non seulement les rationnels avec les dyadiques mais aussi — par une propriété bien connue des développements en fractions continuées — les réels algébriques quadratiques avec les rationnels (par exemple, l'inverse du nombre d'or, (√5−1)/2, ou 0.61803…, s'envoie sur 2/3 exactement, car ils s'obtiennent en alternant branche droite et branche gauche dans un cas sur l'arbre de Stern-Brocot et dans l'autre sur l'arbre dyadique). Ceci suggère toutes sortes de questions. Que peut-on dire, par exemple, du nombre dont l'image par φ est (√5−1)/2 (et donc l'image par φ² — l'itérée double de φ — est 2/3) ? Que peut-on dire des nombres dont l'image par un nombre fini d'application de φ (à la partie fractionnaire) donne un rationnel (ou, de façon équivalente, un dyadique) ? Sont-ils stables par addition et multiplication ? Peut-on les caractériser ? L'image d'un algébrique par φ est-elle un algébrique ? Le nombre 0.42037… qui est un des deux points fixes irrationnels de φ (autrement dit, son parcours dans l'arbre de Stern-Brocot est le même que son parcours dans l'arbre dyadique, c'est-à-dire que son développement en fraction continuée et son écriture binaire sont directement liés) a-t-il des propriétés remarquables ? Est-il transcendant ? Bon, je n'ai pas réfléchi à tout ça, et sans doute beaucoup de ces questions sont-elles stupides (soit parce que leur réponse est évidente soit — ce qui me semble plus probable — parce qu'elle est hors de portée et peu intéressante), mais je suis sûr qu'il y a tout de même quantité de choses fascinantes à dire sur cette fonction φ (tiens, sa dérivée s'annule en tous les dyadiques, mais que peut-on dire de φ′ ailleurs).

Ajout (beaucoup plus tard) : Renseignement pris, la fonction φ en question est également classique et s'appelle la fonction ‘?’ [point d'interrogation] de Minkowski. Dans un même esprit, voir aussi la fonction de Fabius.

↑Entry #0935 [older|newer] / ↑Entrée #0935 [précédente|suivante]

Recent entries / Entrées récentesIndex of all entries / Index de toutes les entrées