Arbre de Stern-Brocot

En mathématiques, l'arbre de Stern-Brocot est une représentation de tous les rationnels strictement positifs, sous forme de fractions irréductibles.

Il a été découvert presque simultanément par le mathématicien allemand Moritz Stern (1858) et par l'horloger français Achille Brocot (1861).

ConstructionModifier

 
Représentation de l'arbre de Stern-Brocot.

L'arbre de Stern-Brocot est un arbre binaire infini dont les noeuds sont étiquetés par les fractions irréductibles. On le construit par récurrence, un étage après l'autre.

L'étage 1 contient uniquement la racine de l'arbre, portant la fraction 1/1.

L'étage p+1 de l'arbre est construit ainsi : on liste toutes les fractions du sous-arbre fini correspondant à l'étage p, lues de gauche à droite. On insère la fraction 0/1 en tête de liste et 1/0 en queue de liste, obtenant ainsi une liste de 2p+1 fractions (voir image). Dans cette liste, une fraction sur deux appartient à l'étage p, une sur quatre à l'étage p − 1, etc.

À chaque fraction appartenant à l'étage p, on associe ses deux filles de niveau p + 1 obtenues en faisant la médiane avec chacune de ses deux voisines dans la liste : la médiane des fractions   et   est la fraction  .

Exemple : les premiers étages de l'arbreModifier

Voici les listes de fractions contenues dans l'arbre après construction de chacun des 4 premiers étages (également représentés sur le dessin) auxquelles on a ajouté 0/1 en premier, 1/0 en dernier. À chaque étage, on a colorié en rouge les fractions ajoutées à cet étage, les autres étant celles des étages précédents ; ainsi les fractions rouges sont les nœuds de l'arbre de Stern-Brocot.

 

Propriétés élémentaires : lien avec les suites de FareyModifier

L'arbre de Stern-Brocot est étroitement lié aux suites de Farey. Rappelons que deux fractions irréductibles m/n et m'/n' sont voisines de Farey si on a :

 

Dans ce cas, on vérifie (voir plus bas) que leur médiane est voisine de Farey, à droite de la première, à gauche de la seconde. Ceci a en particulier comme conséquence que m/n < (m+m')/(n+n') < m'/n' ; on en déduit qu'à chaque étage p de l'arbre de Stern-Brocot, la liste associée des 2p+1 fractions apparaissant dans le sous-arbre est ordonnée de la plus petite à la plus grande et que deux fractions consécutives dans cette liste sont voisines de Farey. Cette dernière propriété entraîne de plus que toutes les fractions apparaissant dans l'arbre sont irréductibles.

Notons que la branche de gauche de l'arbre contient toutes les fractions unitaires, tandis que la branche de droite contient tous les nombres entiers écrits sous forme de fractions de dénominateur égal à 1.

À chaque étage, les dénominateurs des fractions figurant sur la liste associée forment la suite diatomique de Stern.

Arbre de Stern-Brocot et algorithme d'EuclideModifier

L'arbre de Stern-Brocot, comme les suites de Farey, est également lié à l'algorithme d'Euclide ; celui-ci permet en effet, étant donnée une fraction m/n, de calculer le chemin menant de la racine à celle-ci.

On utilise pour cela le théorème de Bachet-Bézout : si l'on suppose que m/n est irréductible, c'est-à-dire que m et n sont premiers entre eux, alors il existe deux entiers m' et n' tels que m'n - mn' = 1 (ou mn' - m'n = 1) ; si de plus on suppose que m et n sont distincts et tous les deux non nuls, alors on peut choisir m' et n' de façon que 0 ≤ m' ≤ m et 0 ≤ n' ≤ n (les coefficients m' et n' satisfaisant toutes ces contraintes sont directement calculés par l'algorithme d'Euclide étendu). Dans ce cas comme on a vu plus haut, les fractions m'/n' et m/n sont voisines de Farey.

On pose alors m'' = m - m' et n'' = n - n' ; si m'n - mn' = 1 alors mn'' - m''n = 1, sinon mn' - m'n = 1 et donc m''n - mn'' = 1. De plus m/n est la fraction médiane de m'/n' et m''/n'' d'où l'on déduit m'/n' < m/n < m'' n'' si mn' - m'n = 1, ou m''/n'' < m/n < m'/n' si m'n - mn' = 1. Dans l'arbre de Stern-Brocot, la fraction m/n est la fille de celle des deux fractions m'/n' et m''/n'' qui a le plus grand dénominateur puisque c'est celle-ci qui se trouve à l'étage le plus bas, et l'on détermine s'il s'agit de la fille gauche ou droite en fonction du signe de m'n - mn'.

Par exemple si l'on considère la fraction 2/5 alors l'algorithme d'Euclide nous donne -2×2 + 1×5 = 1. On en déduit que 1/2 et (2 - 1)/(5 - 2) = 1/3 sont les voisines de 2/5 dans la suite de Farey d'ordre 5 ; comme 1/3 a le plus grand dénominateur elle est la mère de 2/5 ; de plus l'équation -2×2 + 1×5 = 1 implique que 1/2 > 2/5, donc que 1/3 < 2/5, d'où l'on déduit que 2/5 est la fille droite de 1/3.

En itérant l'argument ci-dessus, on peut montrer par récurrence que l'on produit une suite finie de fractions de fille en mère, c'est-à-dire un chemin dans l'arbre remontant de la fraction initiale vers la racine. En particulier ceci donne une démonstration de l'existence de chaque fraction irréductible dans l'arbre.

Énumération des rationnelsModifier

La propriété fondamentale de l'arbre de Stern-Brocot est qu'il contient toutes les fractions irréductibles strictement positives une et une seule fois chacune. On en déduit un procédé pour numéroter tous les rationnels positifs, c'est-à-dire une bijection des rationnels positifs sur les entiers naturels positifs. En bref on associe à un rationnel l'entier dont la représentation en base 2 code le chemin de la racine de l'arbre au rationnel choisi.

Étant donné une fraction on lui associe une suite de 0 et de 1 représentant le chemin issu de la racine de l'arbre et menant à celle-ci. On définit donc deux « pas » : le pas 0 (gauche) et le pas 1 (droite) (dans le livre cité en référence, ceux-ci sont notés L pour left et R pour right). Par exemple le chemin menant à la fraction 2/5 est représenté par la suite (0, 0, 1) : depuis la racine descendre 2 fois à gauche puis 1 fois à droite. Pour simplifier on notera désormais les suites de 0 et de 1 comme des mots binaires, par exemple la suite (0, 0, 1) sera représenté par le mot binaire 001.

L'idée est maintenant de lire le mot binaire associé à une fraction comme la représentation en base 2 d'un entier. Toutefois comme plusieurs mots binaires peuvent représenter le même entier (par exemple les mots 1, 01, 001, ..., représentent tous l'entier 1) on va d'abord préfixer la représentation du chemin par un 1. Si on reprend l'exemple du rationnel 2/5, son chemin est représenté par le mot 001, qui lorsqu'il est préfixé par 1 devient 1001 ce qui se lit comme la représentation en base 2 de l'entier 9. De même le rationnel 3/5 est associé à l'entier  , le rationnel 5/2 à  , etc. Ainsi on affecte un unique numéro à tout rationnel et réciproquement tout entier, écrit en base 2, peut s'interpréter comme un chemin dans l'arbre menant à un rationnel.

Fractions continuesModifier

Toute fraction admet un développement en fraction continue fini dont les coefficients sont les quotients successifs calculés par l'algorithme d'Euclide. Le même algorithme d'Euclide permettant de retrouver le chemin menant de la racine de l'arbre de Stern-Brocot à une fraction donnée, on peut en déduire que le développement en fraction continue code ce chemin. Précisément si [q1; q2, ..., qp, 1] = [q1; q2, ..., qp + 1] est le développement en fraction continue de la fraction m/n, les deux filles de m/n dans l'arbre de Stern-Brocot ont pour développement en fraction continue :

  • [q1; q2, ..., qp + 1, 1] = [q1; q2, ..., qp + 2],
  • [q1; q2, ..., qp, 1, 1] = [q1; q2, ..., qp, 2].

On en déduit par récurrence que la fraction m/n apparaît à l'étage q1 + ... + qn et que la suite (q1 + ... + qn) décrit le chemin y menant depuis la racine 1/1 : descendre q1 pas vers la droite, puis q2 pas vers la gauche, etc. jusqu'à qp pas vers la gauche si p est pair, vers la droite si p est impair.

Autrement dit le chemin menant à la fraction de développement [q1; q2, ..., qp, 1] est codé par le mot 1q10q2...εqpε est le symbole 0 si p est pair, 1 si p est impair.

Par exemple le développement en fraction continue de 2/5 est [0; 2, 1, 1] = [0; 2, 2] ce qui correspond au chemin 001 : 0 pas à droite, puis 2 pas à gauche, puis un pas à droite. On pourra de même calculer que le développement en fraction continue de 17/12 est [1; 2, 2, 2] = [1; 2, 2, 1, 1] tandis que le chemin dans l'arbre menant à 17/12 est représenté par le mot 100110.

Cette correspondance entre fractions continues et arbre de Stern-Brocot est à la base de la définition de la fonction ? de Minkowski[1] : informellement, celle-ci fait correspondre le réel associé à une branche du sous-arbre de l'arbre de Stern-Brocot enraciné en 1/2 (vue comme un développement en fraction continue infini d'un réel plus petit que 1) au réel associé à cette même branche mais dans l'arbre dyadique, c'est-à-dire au réel dont le développement en base 2, vu comme une suite infinie de 0 et de 1, code la branche.

Dans le cas d'une fraction plus petite que 1, dont le développement en fraction continue est donc de la forme [0; q1, ..., qp], la fonction ? considère le chemin en partant de la fraction 1/2 qui est donc codé par la suite q1 - 1, ..., qp et lui associe le rationnel dyadique figurant à la même position dans l'arbre dyadique ; celui-ci se calcule en considérant le mot 1q1-10q2...εqp codant le chemin, en lui ajoutant un 1 à la fin, ce qui donne 1q1-10q2...εqp1 et en lisant le mot obtenu comme le développement en base 2 d'un rationnel dyadique.

Par exemple 2/5 a pour développement [0; 2, 2] = [0; 2, 1, 1]. Le chemin y menant depuis la fraction 1/2 est donc codé par la suite (1, 1) ce qui donne le mot binaire 01111 = 011. Ce mot se lit comme le développement binaire du rationnel dyadique (0,011)2 = 1/4 + 1/8 = 3/8. De même 5/7 a pour développement [0; 1, 2, 1, 1], donc son chemin depuis 1/2 est codé par la suite (0, 2, 1), d'où le mot binaire 0012011 = 1101 ce qui donne finalement le développement binaire (0,1101)2 = 1/2 + 1/4 + 1/16 = 13/16.

Algorithme matricielModifier

On donne ici une méthode utilisant le calcul matriciel pour déterminer une fraction connaissant sa position dans l'arbre de Stern-Brocot qui est une variante du calcul des réduites de son développement en fraction continue. Pour la lisibilité dans cette section on va coder les chemins comme des mots sur l'alphabet composé des deux lettre G (pour les déplacements à gauche) et D (pour les déplacements à droite).

Soit donc un mot S composé de G et de D, on définit f(S) comme la fraction correspondant à S, c'est-à-dire la fraction atteinte en partant de la racine et en suivant le chemin codé par S. Par exemple si S = GGD alors f(S) = 2/5.

On ne considère que des matrices 2x2, ou des matrices colonnes 1x2. Étant donnée une matrice colonne   on note   le rationnel  . Si   et   sont deux matrices colonnes, leur médiane est   ; la terminologie est justifiée par le fait que la fraction   est la médiane au sens défini plus haut des fractions   et  .

On remarque que la médiane de   et   s'obtient en appliquant la matrice   constituée des deux blocs   et   à la matrice colonne   ; et comme   on obtient le même résultat avec la matrice blocs  . En résumé :

 .

Par définition de l'arbre de Stern-Brocot, chaque fraction   y apparaît comme la médiane de deux fractions   et   dont l'une est située à l'étage immédiatement au-dessus. L'idée de l'algorithme matriciel est de calculer   et   plutôt que   ; plus précisément on va calculer la matrice  . On en déduit   puisque l'on vient de voir que  .

Pour cela on remarque que si   est obtenue comme médiane de   et  , alors les deux filles gauche et droite de   sont respectivement les médianes de   et   et de   et  . Autrement dit on passe de la matrice   associée à   aux matrices   associée à sa fille gauche, et   associée à sa fille droite.

Ceci conduit à définir   puisque alors on a :   et  .

Ainsi on a défini les matrices correspondant aux deux descentes gauche et droite d'une mère vers sa fille ; reste à itérer le procédé le long du chemin S (on dit que l'on fait agir le monoïde des mots sur les matrices) par la définition récursive :

  • si   est le mot vide (représentant le chemin de la racine à elle-même) alors   ;
  • si   représente un chemin se terminant par un mouvement gauche, alors   ;
  • si   représente un chemin se terminant par un mouvement droit, alors  .

Notons que la matrice   est de la forme    et   sont les deux matrices colonnes correspondant aux 2 fractions 0/1 et 1/0, dont la médiane est la racine de l'arbre de Stern-Brocot. Ainsi la matrice associé au chemin vide permet bien de calculer la fraction associée au chemin vide, à savoir la racine de l'arbre. On remarque que   est la matrice identité ; c'est pour obtenir cette simplification que l'on a renversé l'ordre des matrices, préférant calculer   plutôt que  .

Ainsi si   est le mot   où les   sont G ou D alors   est la matrice  .

On obtient ainsi une façon très agréable de calculer notre fraction   :

 .

Ainsi sur l'exemple   du chemin menant à la fraction 2/5 on a :

  si bien que finalement   comme attendu.

Voir aussiModifier

Articles connexesModifier

Liens externesModifier

RéférencesModifier