vignette|redresse=2|Représentation de l'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.
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+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'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.
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 :
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 ; on en déduit qu'à chaque étage p de l'arbre de Stern-Brocot, la liste associée des 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 (ou ) ; 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 et (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 et ; si alors , sinon et donc . De plus m/n est la fraction médiane de m/n' et d'où l'on déduit si , ou si . Dans l'arbre de Stern-Brocot, la fraction est la fille de celle des deux fractions et 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 .
Par exemple si l'on considère la fraction 2/5 alors l'algorithme d'Euclide nous donne . On en déduit que 1/2 et 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 implique que , donc que , 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ée 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.
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 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 .
Hérédité : Supposons par récurrence la propriété vérifiée à l'étage p.
Par construction les nouvelles fractions apparaissant à l'étage 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 et m/n qui sont consécutives dans la liste associée à l'étage sont voisines de Farey ce qui se déduit des calculs suivants :
Ainsi toutes les paires m/n et m/n de fractions consécutives de la liste associée à l'étage 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 entraîne en particulier que donc que .
Existence
On a déjà vu en utilisant l'algorithme d'Euclide que toute fraction irréductible apparaît dans l'arbre. On donne ici une autre démonstration.
Considérons une fraction irréductible notée a/b. On va construire quatre suites d'entiers , , et par récurrence sur p :
Pour p = 0 on pose , , et .
À l'étape p trois cas s'offrent à nous : : on pose alors et . : on pose ; ; et . : on pose ; ; et .
Cette définition a plusieurs conséquences facilement vérifiables par récurrence :
les quatre suite d'entiers , , et sont croissantes (mais pas strictement croissantes).
pour tout p si les fractions et sont différentes alors on a , 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 . 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 .
pour tout p si les fractions et sont égales alors elles sont toutes deux égales à a/b et il en est de même de et pour tout .
On veut montrer qu'il existe un p tel que ; si un tel p existe alors en supposant que c'est le plus petit, on a et comme la médiane appartient alors à l'étage cela démontre que l'on a trouvé dans l'arbre.
Comme on a et comme est entier on en déduit . De même de on déduit . En multipliant ces deux inéquations respectivement par et on obtient : .
Or, en utilisant le fait que et sont voisines de Farey on a :
Par conséquent on a finalement : .
La suite d'entiers est donc majorée par . 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 sinon on aurait et par définition l'un au moins (possiblement les deux) de ou de serait égal à la médiane si bien que la somme serait strictement plus grande que , 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 est le développement en fraction continue de la fraction , les deux filles de dans l'arbre de Stern-Brocot ont pour développement en fraction continue : , .