Stern–Brocotier - Stern–Brocot tree

L'arbre de Stern-Brocot et les séquences de Stern-Brocot d'ordre i pour i = 1, 2, 3, 4.

En théorie des nombres , l' arbre de Stern-Brocot est un arbre binaire complet infini dans lequel les sommets correspondent un pour un aux nombres rationnels positifs , dont les valeurs sont ordonnées de gauche à droite comme dans un arbre de recherche .

L'arbre Stern-Brocot a été découvert indépendamment par Moritz Stern  ( 1858 ) et Achille Brocot  ( 1861 ). Stern était un théoricien allemand des nombres ; Brocot était un horloger français qui a utilisé l'arbre Stern-Brocot pour concevoir des systèmes d'engrenages avec un rapport d'engrenage proche d'une valeur souhaitée en trouvant un rapport de nombres lisses proche de cette valeur.

La racine de l'arbre Stern-Brocot correspond au nombre 1. La relation parent-enfant entre les nombres de l'arbre Stern-Brocot peut être définie en termes de fractions continues ou médianes , et d'un chemin dans l'arbre de la racine à tout autre nombre q fournit une séquence d' approximations à q avec des dénominateurs plus petits que q . Parce que l'arbre contient chaque nombre rationnel positif exactement une fois, une première recherche en largeur de l'arbre fournit une méthode de liste de tous les rationnels positifs qui est étroitement liée aux séquences de Farey . Le sous-arbre gauche de l'arbre Stern-Brocot, contenant les nombres rationnels dans la plage (0,1), est appelé l' arbre Farey .

Un arbre de fractions continues

Tout nombre rationnel positif q peut être exprimé comme une fraction continue de la forme

${\displaystyle q=a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{a_{3}+{\cfrac { 1}{\ddots +{\cfrac {1}{a_{k}}}}}}}}}}=[a_{0};a_{1},a_{2},\ldots ,a_{k }]}$

où k et a ₀ sont des entiers non négatifs, et chaque coefficient suivant a _i est un entier positif. Cette représentation n'est pas unique car on a

${\displaystyle [a_{0};a_{1},a_{2},\ldots ,a_{k-1},1]=[a_{0};a_{1},a_{2},\ldots ,a_{k-1}+1]}$

pour toute suite de coefficients a ₀ , ..., a _{k -1} . En utilisant cette identité pour réécrire toute représentation de la première forme dans la seconde forme, on peut obtenir que le coefficient final satisfait a _k 2 (sauf si k = 0 , auquel cas on obtient a ₀  1); avec cette exigence supplémentaire, la représentation devient unique. Alors, à moins que q = 1 , le nombre q a un parent dans l'arbre Stern-Brocot donné par l'expression de fraction continue

${\displaystyle [a_{0};a_{1},a_{2},\ldots ,a_{k}-1],}$

qui dans le cas où a _k = 2 on peut réécrire comme . Par exemple, le nombre rationnel 23 / 16 a la représentation en fraction continue ${\displaystyle [a_{0};a_{1},a_{2},\ldots ,a_{k-1}+1]}$

${\displaystyle {\frac {23}{16}}=1+{\cfrac {1}{2+{\cfrac {1}{3+{\frac {1}{2}}}}}}}=[ 1;2,3,2],}$

donc son parent dans l'arbre Stern-Brocot est le nombre

${\displaystyle [1;2,3,1]=[1;2,4]=1+{\cfrac {1}{2+{\frac {1}{4}}}}={\frac {13 }{9}}.}$

Ce parent est formé en diminuant le dénominateur dans le terme le plus interne de la fraction continue de 1, et en se contractant avec le terme précédent si la fraction devient . ${\displaystyle {\tfrac {1}{1}}}$

Inversement, chaque nombre q dans l'arbre Stern-Brocot a exactement deux enfants : si

${\displaystyle q=[a_{0};a_{1},a_{2},\ldots ,a_{k}]=[a_{0};a_{1},a_{2},\ldots ,a_ {k}-1,1]}$

alors un enfant est le nombre représenté par la fraction continue

${\displaystyle \displaystyle [a_{0};a_{1},a_{2},\ldots ,a_{k}+1]}$

tandis que l'autre enfant est représenté par la fraction continue

${\displaystyle [a_{0};a_{1},a_{2},\ldots ,a_{k}-1,2].}$

L'un de ces enfants a moins de q et c'est l'enfant de gauche ; l'autre est supérieur à q et c'est l'enfant de droite (en fait la première expression donne l'enfant de gauche si k est impair, et l'enfant de droite si k est pair). Par exemple, la représentation de la fraction continue de treize / 9 est [1, 2,4] et ses deux enfants sont [1, 2,5] =  seize / 11 (l'enfant à droite) et [1; 2,3,2] =  23 ⁄ 16 (l'enfant de gauche).

Il est clair que pour chacun l' expression de la fraction continue finie peut se déplacer à plusieurs reprises à son parent, et d' atteindre la racine [1;] = 1 / 1 de l'arbre en plusieurs étapes finiment (dans un ₀ + ... + un _k - 1 étapes pour être précis). Par conséquent, chaque nombre rationnel positif apparaît exactement une fois dans cet arbre. De plus, tous les descendants de l'enfant gauche de n'importe quel nombre q sont inférieurs à q , et tous les descendants de l'enfant droit de q sont supérieurs à q . Les nombres à la profondeur d dans l'arbre sont les nombres pour lesquels la somme des coefficients de fraction continue est d +1 .

Médiatrices et recherche binaire

L'arbre de Stern-Brocot forme un arbre de recherche binaire infini par rapport à l'ordre habituel des nombres rationnels. L'ensemble des nombres rationnels descendant d'un nœud q est défini par l'intervalle ouvert ( L _q , H _q ) où L _q est l'ancêtre de q qui est plus petit que q et le plus proche de lui dans l'arbre (ou L _q  = 0 si q n'a pas d'ancêtre plus petit) tandis que H _q est l'ancêtre de q qui est plus grand que q et le plus proche de lui dans l'arbre (ou H _q  = +∞ si q n'a pas d'ancêtre plus grand).

Le chemin de la racine 1 à un nombre q dans l'arbre Stern-Brocot peut être trouvé par un algorithme de recherche binaire , qui peut être exprimé de manière simple en utilisant des médiatrices . Augmentez les nombres rationnels non négatifs pour inclure une valeur 1/0 (représentant +∞) qui est par définition supérieure à tous les autres rationnels. L' algorithme de recherche binaire se déroule comme suit :

• Initialisez deux valeurs L et H à 0/1 et 1/0, respectivement.
• Jusqu'à ce que q soit trouvé, répétez les étapes suivantes :
  • Soit L = a / b et H = c / d ; calculer la médiane M  = ( a  +  c )/( b  +  d ).
  • Si M est inférieur à q , alors q est dans l'intervalle ouvert ( M , H ); remplacer L par M et continuer.
  • Si M est supérieur à q , alors q est dans l'intervalle ouvert ( L , M ); remplacer H par M et continuer.
  • Dans le cas restant, q = M ; terminer l'algorithme de recherche.

La séquence de valeurs M calculée par cette recherche est exactement la séquence de valeurs sur le chemin de la racine à q dans l'arbre de Stern-Brocot. Chaque intervalle ouvert ( L , H ) apparaissant à une étape de la recherche est l' intervalle ( L _M , H _M ) représentant les descendants de la médiane M . Le parent de q dans l'arbre Stern-Brocot est la dernière médiane trouvée qui n'est pas égale à q .

Cette procédure de recherche binaire peut être utilisée pour convertir des nombres à virgule flottante en nombres rationnels. En s'arrêtant une fois la précision souhaitée atteinte, les nombres à virgule flottante peuvent être approximés à une précision arbitraire. Si un nombre réel x est approximé par n'importe quel nombre rationnel a / b qui n'est pas dans la séquence de médiatrices trouvée par l'algorithme ci-dessus, alors la séquence de médiatrices contient une approximation plus proche de x qui a un dénominateur au plus égal à b ; en ce sens, ces médianes forment les meilleures approximations rationnelles de x .

L'arbre de Stern-Brocot peut lui-même être défini directement en termes de médiatrices : l'enfant de gauche de n'importe quel nombre q est la médiane de q avec son plus petit ancêtre le plus proche, et l'enfant de droite de q est la médiane de q avec son plus grand ancêtre le plus proche. Dans cette formule, q et son ancêtre doivent tous deux être pris en termes les plus bas, et s'il n'y a pas d'ancêtre plus petit ou plus grand, alors 0/1 ou 1/0 doit être utilisé respectivement. Encore une fois, en utilisant 7/5 comme exemple, son plus petit ancêtre le plus proche est 4/3, donc son enfant de gauche est (4 + 7)/(3 + 5) = 11/8, et son plus grand ancêtre le plus proche est 3/2, donc son enfant droit est (7 + 3)/(5 + 2) = 10/7.

Relation avec les séquences de Farey

La séquence de Farey d'ordre n est la séquence triée des fractions dans l'intervalle fermé [0,1] qui ont un dénominateur inférieur ou égal à n . Comme dans la technique de recherche binaire pour générer l'arbre de Stern-Brocot, les séquences de Farey peuvent être construites à l'aide de médiatrices : la séquence de Farey d'ordre n  + 1 est formée à partir de la séquence de Farey d'ordre n en calculant la médiane de chacune de deux valeurs consécutives dans la séquence de Farey d'ordre n , en gardant le sous-ensemble des médianes qui ont un dénominateur exactement égal à n  + 1, et en plaçant ces médianes entre les deux valeurs à partir desquelles elles ont été calculées.

Un processus similaire d'insertion médiane, commençant avec une paire différente de points terminaux d'intervalle [0/1,1/0], peut également être vu pour décrire la construction des sommets à chaque niveau de l'arbre Stern-Brocot. La séquence Stern-Brocot d'ordre 0 est la séquence [0/1,1/0], et la séquence Stern-Brocot d'ordre i est la séquence formée en insérant une médiane entre chaque paire consécutive de valeurs dans la séquence Stern-Brocot d'ordre i  − 1. La séquence Stern-Brocot d'ordre i se compose de toutes les valeurs des i premiers niveaux de l'arbre Stern-Brocot, ainsi que les valeurs limites 0/1 et 1/0, dans l'ordre numérique.

Ainsi, les séquences de Stern-Brocot diffèrent des séquences de Farey de deux manières : elles incluent finalement tous les rationnels positifs, pas seulement les rationnels dans l'intervalle [0,1], et à la n ième étape toutes les médiatrices sont incluses, pas seulement celles avec dénominateur égal à n . La séquence de Farey d'ordre n peut être trouvée par un parcours dans l'ordre du sous-arbre gauche de l'arbre Stern-Brocot, faisant marche arrière chaque fois qu'un nombre de dénominateur supérieur à n est atteint.

Propriétés supplémentaires

Si tous les rationnels sont à la même profondeur dans l'arbre Stern-Brocot, alors ${\displaystyle {{\frac {p_{1}}{q_{1}}},{\frac {p_{2}}{q_{2}}},\dots ,{\frac {p_{n}} {q_{n}}}}}$

${\displaystyle \sum _{k=1}^{n}{\frac {1}{p_{k}q_{k}}}=1}$.

De plus, s'il y a deux fractions consécutives à ou au-dessus d'un certain niveau dans l'arbre (en ce sens que toute fraction entre elles doit être dans un niveau inférieur de l'arbre), alors ${\displaystyle {{\frac {p}{q}}<{\frac {p'}{q'}}}}$

${\displaystyle p'q-pq'=1}$.

Outre les définitions en termes de fractions continues et de médiatrices décrites ci-dessus, l'arbre de Stern-Brocot peut également être défini comme un arbre cartésien pour les nombres rationnels, hiérarchisés par leurs dénominateurs. En d'autres termes, c'est l'arbre de recherche binaire unique des nombres rationnels dans lequel le parent de tout sommet q a un dénominateur plus petit que q (ou si q et son parent sont tous deux des entiers, dans lequel le parent est plus petit que q ). Il résulte de la théorie des arbres cartésiens que le plus petit ancêtre commun de deux nombres q et r dans l'arbre de Stern-Brocot est le nombre rationnel dans l'intervalle fermé [ q ,  r ] qui a le plus petit dénominateur parmi tous les nombres dans cet intervalle .

Permuter les sommets à chaque niveau de l'arbre Stern-Brocot par une permutation par inversion de bits produit un arbre différent, l'arbre Calkin-Wilf , dans lequel les enfants de chaque nombre a / b sont les deux nombres a /( a  +  b ) et ( a  +  b )/ b . Comme l'arbre Stern-Brocot, l'arbre Calkin-Wilf contient chaque nombre rationnel positif exactement une fois, mais ce n'est pas un arbre de recherche binaire.

Voir également

• La fonction de point d'interrogation de Minkowski , dont la définition des arguments rationnels est étroitement liée à l'arbre de Stern-Brocot
• Arbre Calkin–Wilf

Remarques

Les références

• Brocot, Achille (1861), "Calcul des rouages ​​par approximation, nouvelle méthode", Revue Chronométrique , 3 : 186-194.
• Stern, Moritz A. (1858), "Ueber eine zahlentheoretische Funktion" , Journal für die reine und angewandte Mathematik , 55 : 193-220.
• Berstel, Jean ; Lauve, Aaron; Reutenauer, Christophe ; Saliola, Franco V. (2009), Combinatoire des mots. Mots Christoffel et répétitions dans les mots , CRM Monograph Series, 27 , Providence, RI: American Mathematical Society , ISBN 978-0-8218-4480-9, Zbl  1161.68043

Liens externes

• Aiylam, Dhroova, séquences Stern-Brocot modifiées , arXiv : 1301.6807 , Bibcode : 2013arXiv1301.6807A
• Austin, David, Trees, Teeth, and Time: Les mathématiques de l'horlogerie , chronique de l'AMS
• Bogomolny, Alexander , Stern Brocot-Tree , couper le nœud , récupéré le 2008-09-03.
• Sloane, NJA , The Stern-Brocot ou Farey Tree , Encyclopédie en ligne des séquences entières.
• Wildberger, Norman, MF96 : Fractions et l'arbre Stern-Brocot.
• Weisstein, Eric W. "Stern-Brocot Tree" . MathWorld .
• Arbre Stern–Brocot à PlanetMath .
• Fractions infinies , Numberphile
• Amazing Graphs III , Numberphile
• Séquence OEIS A002487 (série diatomique de Stern (ou séquence Stern-Brocot))