Arbre de Stern-Brocot

En mathématiques, l'arbre de Stern-Brocot est une représentation de tous les rationnels strictement positifs, sous forme d'arbre binaire. Chaque nombre rationnel est représenté sous forme de fraction irréductible. Ils sont présents une et une seule fois, et sont tous représentés par cet arbre.

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

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

Ses propriétés permettent de réaliser une bijection entre tous les rationnels et tous les entiers, en codant tout nœud de l'arbre, et donc tous les rationnels, par un nombre binaire et d'établir des lien directs entre cette représentation et les fractions continues.

Construction

L'arbre de Stern-Brocot est un arbre binaire infini dont les nœuds 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 2^p+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 ${\frac {m}{n}}$ et ${\frac {m'}{n'}}$ est la fraction ${\frac {m+m'}{n+n'}}$.

Exemple : les premiers étages de l'arbre

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. Ils se calculent comme la médiane (voir définition ci-dessus) des nombres en noir adjacents.

${\begin{array}{lccccccccccccccccc}{\text{Étage 1 :}}&{\frac {0}{1}}&&&&&&&&{\color {red}{\frac {1}{1}}}&&&&&&&&{\frac {1}{0}}\\{\text{Étage 2 :}}&{\frac {0}{1}}&&&&{\color {red}{\frac {1}{2}}}&&&&{\frac {1}{1}}&&&&{\color {red}{\frac {2}{1}}}&&&&{\frac {1}{0}}\\{\text{Étage 3 :}}&{\frac {0}{1}}&&{\color {red}{\frac {1}{3}}}&&{\frac {1}{2}}&&{\color {red}{\frac {2}{3}}}&&{\frac {1}{1}}&&{\color {red}{\frac {3}{2}}}&&{\frac {2}{1}}&&{\color {red}{\frac {3}{1}}}&&{\frac {1}{0}}\\{\text{Étage 4 :}}&{\frac {0}{1}}&{\color {red}{\frac {1}{4}}}&{\frac {1}{3}}&{\color {red}{\frac {2}{5}}}&{\frac {1}{2}}&{\color {red}{\frac {3}{5}}}&{\frac {2}{3}}&{\color {red}{\frac {3}{4}}}&{\frac {1}{1}}&{\color {red}{\frac {4}{3}}}&{\frac {3}{2}}&{\color {red}{\frac {5}{3}}}&{\frac {2}{1}}&{\color {red}{\frac {5}{2}}}&{\frac {3}{1}}&{\color {red}{\frac {4}{1}}}&{\frac {1}{0}}\end{array}}$

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

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 :

$m'n-mn'=1$

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 2^p+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'Euclide

L'arbre de Stern-Brocot, comme les suites de Farey, est également lié à l'algorithme d'Euclide ; celui-ci permet en effet, étant donné 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 rationnels

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 $(1010)_{2}=10$, le rationnel 5/2 à $(1110)_{2}=14$, 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.

Démonstrations

Irréductibilité de chaque fraction

On montre que chaque fraction apparaissant dans l'arbre est irréductible par récurrence.

On rappelle que la liste associée au p-ième étage de l'arbre de Stern-Brocot est la liste des $2^{p+1}-1$ fractions contenues dans le sous-arbre de hauteur p, lues de gauche à droite, à laquelle on ajoute 0/1 en tête et 1/0 en queue. On va montrer formellement la propriété énoncée plus haut : deux fractions consécutives dans la liste sont voisines de Farey.

Initialisation : À l'étage 0, c'est évident : on a 1.1 – 0.0 = 1.

Hérédité : Supposons par récurrence la propriété vérifiée à l'étage p.

Par construction les nouvelles fractions apparaissant à l'étage p+1 sont des médianes (m + m')/(n + n') où m/n et m'/n' sont consécutives dans la liste associée à l'étage p ; par hypothèse de récurrence on a m'n - mn' = 1. Il faut voir que les fractions m/n, (m+m')/(n+n') et m'/n' qui sont consécutives dans la liste associée à l'étage p+1 sont voisines de Farey ce qui se déduit des calculs suivants :

$(m+m')n-m(n+n')=m'n-mn'=1,$

$m'(n+n')-(m+m')n'=m'n-mn'=1.$

Ainsi toutes les paires m/n et m'/n' de fractions consécutives de la liste associée à l'étage p+1 vérifient m'n - mn' = 1 ce qui est une relation de Bézout d'où l'on déduit en particulier que m et n sont premiers entre eux, donc que m/n (ainsi que m'/n') est irréductible.

Unicité

On veut montrer que chaque fraction strictement positive apparaît au plus une fois dans l'arbre. C'est une conséquence du fait qu'à chaque étage la liste associée est strictement croissante, qui lui-même est conséquence du fait démontré ci-dessus que les fractions consécutives dans la liste associée à l'étage p sont voisines de Farey ; en effet m'n - mn' = 1 entraîne en particulier que m'/n' - m/n = 1/nn' > 0 donc que m/n < m'/n'.

Existence

On a déjà vu en utilisant l'algorithme d'Euclide que toute fraction irréductible apparaît dans l'arbre. On donne en donne ici une autre démonstration.

Considérons une fraction irréductible notée a/b. On va construire quatre suites d'entiers $(m_{p})$, $(n_{p})$, $(m'_{p})$ et $(n'_{p})$ par récurrence sur p :

Pour p = 0 on pose $m_{0}=0$, $n_{0}=1$, $m'_{0}=1$ et $n'_{0}=0$.

À l'étape p trois cas s'offrent à nous :

• ${\frac {m_{p}+m'_{p}}{n_{p}+n'_{p}}}={\frac {a}{b}}$ : on pose alors $m_{p+1}=m'_{p+1}=a$ et $n_{p+1}=n'_{p+1}=b$.
• ${\frac {m_{p}+m'_{p}}{n_{p}+n'_{p}}}<{\frac {a}{b}}$ : on pose $m_{p+1}=m_{p}+m'_{p}$ ; $n_{p+1}=n_{p}+n'_{p}$ ; $m'_{p+1}=m'_{p}$ et $n'_{p+1}=n'_{p}$.
• ${\frac {m+m'}{n+n'}}>{\frac {a}{b}}$ : on pose $m_{p+1}=m_{p}$ ; $n_{p+1}=n_{p}$ ; $m'_{p+1}=m_{p}+m'_{p}$ et $n'_{p+1}=n_{p}+n'_{p}$.

Cette définition a plusieurs conséquences facilement vérifiables par récurrence :

• les quatre suite d'entiers $(m_{p})$, $(n_{p})$, $(m'_{p})$ et $(n'_{p})$ sont croissantes (mais pas strictement croissantes).

• pour tout p si les fractions $m_{p}/n_{p}$ et $m'_{p}/n'_{p}$ sont différentes alors on a $m_{p}/n_{p}<a/b<m'_{p}/n'_{p}$, elles sont consécutives dans la liste associée à l'étage p, donc en particulier voisines de Farey, ce qui entraîne notamment qu'elles sont irréductibles. De plus l'une des deux appartient à l'étage p et donc leur médiane appartient à l'étage p+1. En effet dans la liste associée à l'étage p une fraction sur deux appartient à l'étage p, par conséquent la médiane de deux fractions consécutives appartient à l'étage p+1.

• pour tout p si les fractions $m_{p}/n_{p}$ et $m'_{p}/n'_{p}$ sont égales alors elles sont toutes deux égales à a/b et il en est de même de $m_{q}/n_{q}$ et $m'_{q}/n'_{q}$ pour tout $q\geq p$.

On veut montrer qu'il existe un p tel que $a/b=m_{p+1}/n_{p+1}=m'_{p+1}/n'_{p+1}$ ; si un tel p existe alors en supposant que c'est le plus petit, on a $a/b=(m_{p}+m'_{p})/(n_{p}+n'_{p})$ et comme la médiane appartient alors à l'étage p+1 cela démontre que l'on a trouvé $a/b$ dans l'arbre.

Comme $a/b>m_{p}/n_{p}$ on a $an_{p}-bm_{p}>0$ et comme $an_{p}-bm_{p}$ est entier on en déduit $an_{p}-bm_{p}\geq 1$. De même de $a/b<m'_{p}/n'_{p}$ on déduit $bm'_{p}-an'_{p}\geq 1$. En multipliant ces deux inéquations respectivement par $m'_{p}+n'_{p}$ et $m_{p}+n_{p}$ on obtient : $(m'_{p}+n'_{p})(an_{p}-bm_{p})+(m_{p}+n_{p})(bm'_{p}-an'_{p})\geq m'_{p}+n'_{p}+m_{p}+n_{p}$.

Or, en utilisant le fait que $m_{p}/n_{p}$ et $m'_{p}/n'_{p}$ sont voisines de Farey on a :

${\begin{aligned}(m'_{p}+n'_{p})(an_{p}-bm_{p})+(m_{p}+n_{p})(bm'_{p}-an'_{p})&=am'_{p}n_{p}+an_{p}n'_{p}-bm_{p}m'_{p}-bm_{p}n'_{p}+bm_{p}m'_{p}+bm'_{p}n_{p}-am_{p}n'_{p}-an_{p}n'_{p}\\&=a(m'_{p}n_{p}-m_{p}n'_{p})+b(m'_{p}n_{p}-m_{p}n'_{p})\\&=a+b\end{aligned}}$

Par conséquent on a finalement : $a+b\geq m'_{p}+n'_{p}+m_{p}+n_{p}$.

La suite d'entiers $(m'_{p}+n'_{p}+m_{p}+n_{p})$ est donc majorée par $a+b$. Elle ne peut donc être strictement croissante mais elle est croissante car somme de quatre suites croissantes, donc il existe un rang p à partir duquel elle est stationnaire. Mais alors on doit avoir $m_{p}/n_{p}=m'_{p}/n'_{p}=a/b$ sinon on aurait $m_{p}/n_{p}<a/b<m'_{p}/n'_{p}$ et par définition l'un au moins (possiblement les deux) de $m_{p+1}/n_{p+1}$ ou de $m'_{p+1}/n'_{p+1}$ serait égal à la médiane $(m_{p}+m_{p+1})/(n_{p}+n_{p+1})$ si bien que la somme $m_{p+1}+m'_{p+1}+n_{p+1}+n'_{p+1}$ serait strictement plus grande que $m_{p}+m'_{p}+n_{p}+n'_{p}$, contredisant la stationnarité de la suite à partir de p.

Comparaison avec l'algorithme d'Euclide

L'algorithme d'Euclide permet de montrer la présence d'une fraction dans l'arbre en partant de celle-ci et par divisions euclidiennes successives de remonter vers la racine, construisant donc un chemin remontant de la fraction à la racine. La démonstration ci-dessus procède dans l'autre sens : partant de la racine on produit une suite de fractions qui se termine ultimement sur celle donnée initialement, produisant un chemin qui descend de la racine vers celle-ci. Noter que le même algorithme appliqué à un nombre réel plutôt qu'à une fraction permet de construire la branche infinie de fractions approximant ce réel.

Fractions continues

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 [q₁; q₂, ..., q_p, 1] = [q₁; q₂, ..., q_p + 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 :

• [q₁; q₂, ..., q_p + 1, 1] = [q₁; q₂, ..., q_p + 2],
• [q₁; q₂, ..., q_p, 1, 1] = [q₁; q₂, ..., q_p, 2].

On en déduit par récurrence que la fraction m/n apparaît à l'étage q₁ + ... + q_n et que la suite (q₁ + ... + q_n) décrit le chemin y menant depuis la racine 1/1 : descendre q₁ pas vers la droite, puis q₂ pas vers la gauche, etc. jusqu'à q_p 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 [q₁; q₂, ..., q_p, 1] est codé par le mot 1^q₁0^q₂...ε^q_p où ε 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.

Démonstration

Appelons hauteur de $m/n$ le nombre $N=q_{1}+\cdots +q_{p}$. On suppose par récurrence que toute fraction de hauteur inférieure ou égale à $N$ apparaît à l'étage $N$ dans l'arbre de Stern-Brocot. On remarque tout d'abord que les deux filles présumées de $m/n$ sont de hauteur $N+1$ et comme elles apparaissent à l'étage $N+1$ (leur mère étant à l'étage $N$), on a bien démontré par récurrence l'égalité entre hauteur et étage de l'arbre.

Reste à démontrer que ces deux fractions sont bien les filles de $m/n$. Pour cela on va trouver les deux voisines de $m/n$ dans la liste associée à l'étage $N$.

Commençons par deux rappels préliminaires. Parmi les propriétés des voisinages de Farey il y a en particulier le fait que lorsque $a/b$ et $a'/b'$ sont voisines de Farey alors toute fraction $a''/b''$ située strictement entre les deux est obtenue en itérant l'opération de médiane à partir de $a/b$ et $a'/b'$, donc apparaît forcément à un étage supérieur aux deux dans l'arbre de Stern-Brocot.

D'autre part si $[q_{1};q_{2},\dots ,q_{p}]$ est une fraction continue, ses réduites $m_{k}/n_{k}=[q_{1};q_{2},...,q_{k}]$ pour $k=1,\dots ,p$ sont données par la récurrence :

• $m_{-1}=0$, $m_{0}=1$, $n_{-1}=1$, $n_{0}=0$ ;
• $m_{k+1}=m_{k}q_{k+1}+m_{k-1}$, $n_{k+1}=n_{k}q_{k+1}+n_{k-1}$.

En particulier, comme $m/n=[q_{1},\dots ,q_{p}+1]$ on a

${\frac {m}{n}}={\frac {m_{p-1}(q_{p}+1)+m_{p-2}}{n_{p-1}(q_{p}+1)+n_{p-2}}}={\frac {m_{p-1}q_{p}+m_{p-2}+m_{p-1}}{n_{p-1}q_{p}+n_{p-2}+n_{p-1}}}={\frac {m_{p}+m_{p-1}}{n_{p}+n_{p-1}}}$

Considérons la fraction continue $m'/n'=[q_{1},\dots ,q_{n-1}]=m_{p-1}/n_{p-1}$. Celle-ci est une voisine de Farey de $m/n$. En effet on peut faire le calcul suivant :

${\begin{aligned}m_{k+1}n_{k}-m_{k}n_{k+1}&=(m_{k}q_{k+1}+m_{k-1})n_{k}-m_{k}(n_{k}q_{k+1}+n_{k-1})\\&=-(m_{k}n_{k-1}-m_{k-1}n_{k})\end{aligned}}$

d'où l'on déduit par récurrence que $m_{k+1}n_{k}-m_{k}n_{k+1}=(-1)^{k+1}$ et donc que $m_{k}/n_{k}=[q_{1},\dots ,q_{k}]$ et $m_{k+1}/n_{k+1}=[q_{1},\dots ,q_{k+1}]$ sont voisines de Farey pour $k=1,\dots ,p$. Autrement dit les réduites de deux fractions continues dont la première est un préfixe de la seconde et dont les longueurs diffèrent de 1 sont voisines de Farey. Par conséquent $m/n=[q_{1},\dots ,q_{p}+1]$ et $m'/n'=[q_{1},\dots ,q_{p-1}]$ sont voisines de Farey. Or $m/n$ est de hauteur $N$ tandis que $m'/n'$ est de hauteur $N'=q_{1}+\cdots q_{p-1}-1<N$, par hypothèse de récurrence $m'/n'$ est à l'étage $N'$, donc toutes deux sont dans la liste associée à l'étage $N$, et sont donc consécutives dans celle-ci.

On en déduit que l'une des deux filles de $m/n$ à l'étage $N+1$ est leur médiane:

${\begin{aligned}{\frac {m+m'}{n+n'}}&={\frac {m_{p-1}(q_{p}+1)+m_{p-2}+m_{p-1}}{n_{p-1}(q_{p}+1)+n_{p-2}+n_{p-1}}}\\&={\frac {m_{p-1}(q_{p}+2)+m_{p-2}}{n_{p-1}(q_{p}+2)+n_{p-2}}}\end{aligned}}$

qui est la réduite de la fraction continue $[q_{1},\dots ,q_{p}+2]$ comme attendu.

Considérons maintenant la fraction $m''/n''=[q_{1},\dots ,q_{p}]=m_{p}/n_{p}$. Alors on a:

${\begin{aligned}m''n-mn''&=m_{p}(n_{p}+n_{p-1})-(m_{p}+m_{p-1})n_{p}\\&=m_{p}n_{p-1}-m_{p-1}n_{p}\\&=(-1)^{p}\end{aligned}}$

si bien que à nouveau $m''/n''$ et $m/n$ sont voisines de Farey. Mais $m''/n''$ est de hauteur $N''=q_{1}+\cdots +q_{p}-1=N-1$ donc par récurrence, $m''/n''$ est à l'étage $N-1$, donc est voisine de $m/n$ dans la liste associée à l'étage $N$. Par conséquent l'autre fille de $m/n$ est leur médiane:

${\begin{aligned}{\frac {m+m''}{n+n''}}&={\frac {m_{p}+m_{p-1}+m_{p}}{n_{p}+n_{p-1}+n_{p}}}\\&={\frac {2m_{p}+m_{p-1}}{2n_{p}+n_{p-1}}}\end{aligned}}$

qui est la réduite de la fraction continue $[q_{1},\dots ,q_{p},2]$ comme annoncé.

Cette correspondance entre fractions continues et arbre de Stern-Brocot est à la base de la définition de la fonction ? de Minkowski : 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; q₁, ..., q_p], la fonction ? considère le chemin en partant de la fraction 1/2 qui est donc codé par la suite q₁ - 1, ..., q_p et lui associe le rationnel dyadique figurant à la même position dans l'arbre dyadique ; celui-ci se calcule en considérant le mot 1^q₁-10^q₂...ε^q_p codant le chemin, en lui ajoutant un 1 à la fin, ce qui donne 1^q₁-10^q₂...ε^q_p1 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 0¹1¹1 = 011. Ce mot se lit comme le développement binaire du rationnel dyadique (0,011)₂ = 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 0⁰1²0¹1 = 1101 ce qui donne finalement le développement binaire (0,1101)₂ = 1/2 + 1/4 + 1/16 = 13/16.

Algorithme matriciel

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é une matrice colonne ${\begin{pmatrix}m\\n\end{pmatrix}}$ on note $q{\begin{pmatrix}m\\n\end{pmatrix}}$ le rationnel ${\frac {m}{n}}$. Si $V_{1}$ et $V_{2}$ sont deux matrices colonnes, leur médiane est $V_{1}+V_{2}$ ; la terminologie est justifiée par le fait que la fraction $q(V_{1}+V_{2})$ est la médiane au sens défini plus haut des fractions $q(V_{1})$ et $q(V_{2})$.

On remarque que la médiane de $V_{1}$ et $V_{2}$ s'obtient en appliquant la matrice ${\begin{pmatrix}V_{1}&V_{2}\end{pmatrix}}$ constituée des deux blocs $V_{1}$ et $V_{2}$ à la matrice colonne ${\begin{pmatrix}1\\1\end{pmatrix}}$ ; et comme $V_{1}+V_{2}=V_{2}+V_{1}$ on obtient le même résultat avec la matrice blocs ${\begin{pmatrix}V_{2}&V_{1}\end{pmatrix}}$. En résumé :

$V_{1}+V_{2}={\begin{pmatrix}V_{1}&V_{2}\end{pmatrix}}{\begin{pmatrix}1\\1\end{pmatrix}}={\begin{pmatrix}V_{2}&V_{1}\end{pmatrix}}{\begin{pmatrix}1\\1\end{pmatrix}}$.

Par définition de l'arbre de Stern-Brocot, chaque fraction $q(V)$ y apparaît comme la médiane de deux fractions $q(P_{1})$ et $q(P_{2})$ dont l'une est située à l'étage immédiatement au-dessus. L'idée de l'algorithme matriciel est de calculer $P_{1}$ et $P_{2}$ plutôt que $V$ ; plus précisément on va calculer la matrice ${\begin{pmatrix}P_{2}&P_{1}\end{pmatrix}}$. On en déduit $V$ puisque l'on vient de voir que $V={\begin{pmatrix}P_{2}&P_{1}\end{pmatrix}}{\begin{pmatrix}1\\1\end{pmatrix}}$.

Pour cela on remarque que si $q(V)$ est obtenue comme médiane de $q(P_{1})$ et $q(P_{2})$, alors les deux filles gauche et droite de $q(V)$ sont respectivement les médianes de $q(P_{1})$ et $q(V)$ et de $q(V)$ et $q(P_{2})$. Autrement dit on passe de la matrice ${\begin{pmatrix}P_{2}&P_{1}\end{pmatrix}}$ associée à $V=P_{1}+P_{2}$ aux matrices ${\begin{pmatrix}P_{1}+P_{2}&P_{1}\end{pmatrix}}$ associée à sa fille gauche, et ${\begin{pmatrix}P_{2}&P_{1}+P_{2}\end{pmatrix}}$ associée à sa fille droite.

Ceci conduit à définir ${\hat {G}}={\begin{pmatrix}1&0\\1&1\end{pmatrix}},\,{\hat {D}}={\begin{pmatrix}1&1\\0&1\end{pmatrix}}$ puisque alors on a : ${\begin{pmatrix}P_{2}&P_{1}\end{pmatrix}}{\hat {G}}={\begin{pmatrix}P_{2}+P_{1}&P_{1}\end{pmatrix}}$ et ${\begin{pmatrix}P_{2}&P_{1}\end{pmatrix}}{\hat {D}}={\begin{pmatrix}P_{2}&P_{2}+P_{1}\end{pmatrix}}$.

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 $S=\epsilon$ est le mot vide (représentant le chemin de la racine à elle-même) alors ${\hat {S}}={\hat {\epsilon }}={\begin{pmatrix}1&0\\0&1\end{pmatrix}}$ ;
• si $S=TG$ représente un chemin se terminant par un mouvement gauche, alors ${\hat {S}}={\hat {T}}{\hat {G}}$ ;
• si $S=TD$ représente un chemin se terminant par un mouvement droit, alors ${\hat {S}}={\hat {T}}{\hat {D}}$.

Notons que la matrice ${\hat {\epsilon }}$ est de la forme ${\begin{pmatrix}V_{2}&V_{1}\end{pmatrix}}$ où $V_{1}={\begin{pmatrix}0\\1\end{pmatrix}}$ et $V_{2}={\begin{pmatrix}1\\0\end{pmatrix}}$ 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 ${\hat {\epsilon }}$ est la matrice identité ; c'est pour obtenir cette simplification que l'on a renversé l'ordre des matrices, préférant calculer ${\begin{pmatrix}P_{2}&P_{1}\end{pmatrix}}$ plutôt que ${\begin{pmatrix}P_{2}&P_{1}\end{pmatrix}}$.

Ainsi si $S$ est le mot $S_{1}S_{2}\ldots S_{n}$ où les $S_{i}$ sont G ou D alors ${\hat {S}}$ est la matrice ${\hat {\epsilon }}{\hat {S}}_{1}\dots {\hat {S}}_{n}={\hat {S}}_{1}\dots {\hat {S}}_{n}$.

On obtient ainsi une façon très agréable de calculer notre fraction $f(S)$ :

$f(S)=q\left({\hat {S}}_{1}{\hat {S}}_{2}\ldots {\hat {S}}_{n}{\begin{pmatrix}1\\1\end{pmatrix}}\right)$.

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

${\hat {S}}={\hat {G}}{\hat {G}}{\hat {D}}={\begin{pmatrix}1&0\\1&1\end{pmatrix}}{\begin{pmatrix}1&0\\1&1\end{pmatrix}}{\begin{pmatrix}1&1\\0&1\end{pmatrix}}={\begin{pmatrix}1&1\\2&3\end{pmatrix}}$ si bien que finalement ${\hat {S}}{\begin{pmatrix}1\\1\end{pmatrix}}={\begin{pmatrix}2\\5\end{pmatrix}}$ comme attendu.

Voir aussi

Articles connexes

• Arbre binaire
• Algorithme d'Euclide
• Suite de Farey
• Suite diatomique de Stern
• Fonction point d'interrogation
• Arbre de Calkin-Wilf

Liens externes

• Robert Ferréol, « Addition des cancres, suites de Brocot et friandises associées », Quadrature, n^o 36,‎ avril mai juin 1999, p. 13 - 24 (lire en ligne)

• Roger Mansuy, « Achille Brocot, mathématicien à ses heures », sur CultureMATH, 20 mai 2008
• J.P. Delahaye, « Mathématique des engrenages », Pour La Science, n^o 537,‎ juillet 2022, p. 84 (lire en ligne )
• (en) Eric W. Weisstein, « Stern-Brocot Tree », sur MathWorld

Références

• Mathématiques concrètes (2^e édition) de Ronald Graham, Donald Knuth et Oren Patashnik (ISBN 978-2-7117-4824-2)