Árbol de Stern-Brocot

En teoría de números , el árbol de Stern-Brocot es un árbol binario completo infinito cuyos vértices se corresponden uno a uno con los números racionales positivos , cuyos valores están ordenados de izquierda a derecha como en un árbol de búsqueda binaria .

El árbol de Stern-Brocot fue introducido independientemente por Moritz Stern ( 1858 ) y Achille Brocot ( 1861 ) . Stern era un teórico de números alemán; Brocot era un relojero francés que utilizó el árbol de Stern-Brocot para diseñar sistemas de engranajes con una relación de transmisión cercana a un valor deseado, hallando una relación de números suaves próximos a dicho valor.  

La raíz del árbol de Stern-Brocot corresponde al número 1. La relación padre-hijo entre los números en el árbol de Stern-Brocot se puede definir en términos de fracciones continuas simples o medianas , y un camino en el árbol desde la raíz hasta cualquier otro número q proporciona una secuencia de aproximaciones a q con denominadores más pequeños que q . Dado que el árbol contiene cada número racional positivo exactamente una vez, una búsqueda en anchura del árbol proporciona un método para listar todos los racionales positivos que está estrechamente relacionado con las secuencias de Farey . El subárbol izquierdo del árbol de Stern-Brocot, que contiene los números racionales en el rango (0,1) , se llama árbol de Farey .

Cada vértice del árbol puede asociarse con una terna de fracciones que consta de tres fracciones en la misma fila que el vértice, a saber, la fracción inmediatamente a la izquierda del vértice, la fracción en el vértice mismo y la fracción inmediatamente a la derecha del vértice. (Véase la figura anterior). Las fracciones izquierda y derecha no corresponden a vértices en la misma fila que el vértice, sino a vértices en alguna fila anterior. Cada una de estas fracciones puede entenderse como una etiqueta de la región del plano delimitada por dos caminos infinitos que descienden del vértice anterior etiquetado por la misma fracción. El segundo elemento de una terna siempre será la mediana del primer y tercer elemento. Por ejemplo, la raíz está asociada con${\displaystyle {\bigl (}{\tfrac {0}{1}},{\tfrac {1}{1}},{\tfrac {1}{0}}{\bigr )}}$y sus descendientes izquierdo y derecho están asociados con${\displaystyle {\bigl (}{\tfrac {0}{1}},{\tfrac {1}{2}},{\tfrac {1}{1}}{\bigr )}}$y${\displaystyle {\bigl (}{\tfrac {1}{1}},{\tfrac {2}{1}},{\tfrac {1}{0}}{\bigr )}.}$

El árbol se genera mediante la siguiente regla: $${\displaystyle {\begin{array}{ccccc}&&\left({\dfrac {a}{b}},{\dfrac {c}{d}},{\dfrac {e}{f}}\right)&&\\&\swarrow &&\searrow &\\\left({\dfrac {a}{b}},{\dfrac {a+c}{b+d}},{\dfrac {c}{d}}\right)&&&&\left({\dfrac {c}{d}},{\dfrac {c+e}{d+f}},{\dfrac {e}{f}}\right)\end{array}}}$$

La relación entre padres e hijos también puede entenderse en términos de fracciones continuas. Todo número racional positivo q puede expresarse como una fracción continua de la forma $${\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}]}$$ donde k y a ₀ son enteros no negativos, y cada coeficiente subsiguiente a _i es un entero positivo. Esta representación no es única porque $${\displaystyle [a_{0};a_{1},a_{2},\ldots ,a_{k-1},1]=[a_{0};a_{1},a_{2},\ldots ,a_{k-1}+1],}$$ pero al usar esta equivalencia para reemplazar cada fracción continua que termina en uno por una fracción continua más corta, se demuestra que cada número racional tiene una representación única en la que el último coeficiente es mayor que uno. Entonces, a menos que q = 1 , el número q tiene un padre en el árbol de Stern-Brocot dado por la expresión de fracción continua. $${\displaystyle [a_{0};a_{1},a_{2},\ldots ,a_{k}-1].}$$De forma equivalente , este término padre se forma disminuyendo el denominador del término más interno de la fracción continua en 1 y  contrayéndolo con el término anterior si la fracción se convierte en 1/1 . Por ejemplo, el número racional 23/16 tiene la representación de fracción continua .$${\displaystyle {\frac {23}{16}}=1+{\cfrac {1}{2+{\cfrac {1}{3+{\frac {1}{2}}}}}}=[1;2,3,2],}$$ por lo que su padre en el árbol de Stern-Brocot es el número $${\displaystyle [1;2,3,1]=[1;2,4]=1+{\cfrac {1}{2+{\frac {1}{4}}}}={\frac {13}{9}}.}$$

Por el contrario, cada número q en el árbol de Stern-Brocot tiene exactamente dos hijos: si $${\displaystyle q=[a_{0};a_{1},a_{2},\ldots ,a_{k}]=[a_{0};a_{1},a_{2},\ldots ,a_{k}-1,1]}$$ entonces un niño es el número representado por la fracción continua $${\displaystyle \displaystyle [a_{0};a_{1},a_{2},\ldots ,a_{k}+1]}$$ mientras que el otro niño está representado por la fracción continua. $${\displaystyle [a_{0};a_{1},a_{2},\ldots ,a_{k}-1,2].}$$ Uno de estos hijos es menor que q y este es el hijo izquierdo; el otro es mayor que q y es el hijo derecho (de hecho, la expresión anterior da el hijo izquierdo si k es impar, y el hijo derecho si k es par). Por ejemplo, la representación en fracción continua de 13/9 es [ 1 ;2,4] y sus dos hijos son [1;2,5] = 16/11 ( el hijo derecho) y [ 1;2,3,2 ] = 23/16 ( el hijo izquierdo ) .

Es evidente que para cada expresión de fracción continua finita se puede avanzar repetidamente a su padre y alcanzar la raíz [1;] = 1 / 1 del árbol en un número finito de pasos (en a ₀ + ... + a _k − 1 pasos , para ser precisos). Por lo tanto, cada número racional positivo aparece exactamente una vez en este árbol. Además , todos los descendientes del hijo izquierdo de cualquier número q son menores que q , y todos los descendientes del hijo derecho de q son mayores que q . Los números en la profundidad d del árbol son aquellos para los cuales la suma de los coeficientes de la fracción continua es d + 1 .

El árbol de Stern-Brocot forma un árbol de búsqueda binaria infinito con respecto al orden usual de los números racionales. ^{[ 1 ] [ 2 ]} El conjunto de números racionales que descienden de un nodo q se define por el intervalo abierto ( L _q , H _q ) donde L _q es el ancestro de q que es menor que q y más cercano a él en el árbol (o L _q = 0 si q no tiene un ancestro menor) mientras que H _q es el ancestro de q que es mayor que q y más cercano a él en el árbol (o H _q = +∞ si q no tiene un ancestro mayor).

El camino desde la raíz 1 hasta un número q en el árbol de Stern-Brocot se puede encontrar mediante un algoritmo de búsqueda binaria , que se puede expresar de forma sencilla utilizando medianas . Se amplían los números racionales no negativos para incluir un valor 1/0 ( que representa +∞) , el cual, por definición , es mayor que todos los demás racionales. El algoritmo de búsqueda binaria procede de la siguiente manera:

• Inicialice dos valores L y H a ⁠ 0 / 1 ⁠ y ⁠ 1 / 0 ⁠ , respectivamente.
• Hasta que se encuentre q , repita los siguientes pasos:
  • Sea L = ⁠ a / b ⁠ y H = ⁠ c / d ⁠ ; calcule la mediana.${\displaystyle M=L\oplus H={\frac {a+c}{b+d}}.}$
  • Si M es menor que q , entonces q está en el intervalo abierto ( M , H ) ; reemplace L por M y continúe.
  • Si M es mayor que q , entonces q está en el intervalo abierto ( L , M ) ; reemplace H por M y continúe.
  • En el caso restante, q = M ; finalizar el algoritmo de búsqueda.

La secuencia de valores M calculada por esta búsqueda es exactamente la secuencia de valores en el camino desde la raíz hasta q en el árbol de Stern-Brocot. Cada intervalo abierto ₍ L , H ) que aparece en algún paso de la búsqueda es el intervalo ( LM , HM ) que representa a los descendientes de la mediana M. El padre de q en el árbol _de Stern-Brocot es la última mediana encontrada que no es igual a q .

Este procedimiento de búsqueda binaria se puede utilizar para convertir números de punto flotante en números racionales. Al detenerse una vez que se alcanza la precisión deseada, los números de punto flotante se pueden aproximar a una precisión arbitraria. ^{[ 3 ]} Si un número real x se aproxima mediante cualquier número racional a / b que no esté en la secuencia de medianas encontradas por el algoritmo anterior, entonces la secuencia de medianas contiene una aproximación más cercana a x que tiene un denominador como máximo igual a b ; en ese sentido, estas medianas forman las mejores aproximaciones racionales a x .

El árbol de Stern-Brocot puede definirse directamente en términos de medianas: el hijo izquierdo de cualquier número q es la mediana de q con su ancestro menor más cercano, y el hijo derecho de q es la mediana de q con su ancestro mayor más cercano . En esta fórmula, tanto q como su ancestro deben tomarse en su mínima expresión, y si no hay un ancestro menor o mayor , entonces se deben usar 0/1 o 1/0 respectivamente . Nuevamente, usando ⁠ 7 / 5 ⁠ como ejemplo, su ancestro menor más cercano es ⁠ 4 / 3 ⁠ , por lo que su hijo izquierdo es ⁠ 4 + ​​7 / 3 + 5 ⁠ = ⁠ 11 / 8 ⁠ , y su ancestro mayor más cercano es ⁠ 3 / 2 ⁠ , por lo que su hijo derecho es ⁠ 7 + 3 / 5 + 2 ⁠ = ⁠ 10 / 7 ⁠ .

La secuencia de Farey de orden n es la secuencia ordenada de fracciones en el intervalo cerrado [0,1] cuyo denominador es menor o igual a n . Al igual que en la técnica de búsqueda binaria para generar el árbol de Stern-Brocot, las secuencias de Farey se pueden construir utilizando medianas: la secuencia de Farey de orden n + 1 se forma a partir de la secuencia de Farey de orden n calculando la mediana de cada par de valores consecutivos en la secuencia de Farey de orden n , conservando el subconjunto de medianas cuyo denominador es exactamente igual a n + 1 , y colocando estas medianas entre los dos valores a partir de los cuales se calcularon.

Un proceso similar de inserción de la mediana, comenzando con un par diferente de puntos finales del intervalo.${\displaystyle {\bigl [}{\tfrac {0}{1}},{\tfrac {1}{0}}{\bigr ]},}$También puede verse que describe la construcción de los vértices en cada nivel del árbol de Stern-Brocot. La secuencia de Stern-Brocot de orden 0 es la secuencia${\displaystyle {\bigl [}{\tfrac {0}{1}},{\tfrac {1}{0}}{\bigr ]},}$y la secuencia de Stern-Brocot de orden i es la secuencia formada al insertar una mediana entre cada par consecutivo de valores en la secuencia de Stern-Brocot de orden i − 1 . La secuencia de Stern-Brocot de orden i consta de todos los valores en los primeros i niveles del árbol de Stern-Brocot, junto con los valores límite ⁠ 0 / 1 ⁠ y ⁠ 1 / 0 ⁠ , en orden numérico.

Así, las secuencias de Stern-Brocot difieren de las secuencias de Farey en dos aspectos: incluyen todos los racionales positivos, no solo los racionales dentro del intervalo [0,1] , y en el paso n se incluyen todas las medianas, no solo las que tienen denominador igual a n . La secuencia de Farey de orden n se puede encontrar mediante un recorrido en orden del subárbol izquierdo del árbol de Stern-Brocot, retrocediendo cada vez que se alcanza un número con denominador mayor que n .

Si${\displaystyle {\tfrac {p_{1}}{q_{1}}},{\tfrac {p_{2}}{q_{2}}},\dots ,{\tfrac {p_{n}}{q_{n}}}}$Si todos los racionales se encuentran a la misma profundidad en el árbol de Stern-Brocot, entonces...

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

Además, si${\displaystyle {\tfrac {p}{q}}<{\tfrac {p'}{q'}}}$son dos fracciones consecutivas en o por encima de un cierto nivel en el árbol (en el sentido de que cualquier fracción entre ellas debe estar en un nivel inferior del árbol), entonces ^{[ 4 ]}

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

Además de las definiciones en términos de fracciones continuas y medianas descritas anteriormente, el árbol de Stern-Brocot también puede definirse como un árbol cartesiano para los números racionales, priorizado por sus denominadores. En otras palabras, es el único árbol de búsqueda binaria de los números racionales en el que el padre de cualquier vértice q tiene un denominador menor que q (o, si q y su padre son ambos enteros, en el que el padre es menor que q ). De la teoría de los árboles cartesianos se deduce que el ancestro común más bajo de dos números cualesquiera q y r en el árbol de Stern-Brocot es el número racional en el intervalo cerrado [ q , r ] que tiene el denominador más pequeño entre todos los números de este intervalo.

Al permutar los vértices de cada nivel del árbol de Stern-Brocot mediante una permutación de inversión de bits, se obtiene un árbol diferente, el árbol de Calkin-Wilf , en el que los hijos de cada número a / b son los dos números a / a + b y a + b / b . Al igual que el árbol de Stern-Brocot, el árbol de Calkin-Wilf contiene cada número racional positivo exactamente una vez, pero no es un árbol de búsqueda binaria .

• La función de interrogación de Minkowski , cuya definición para argumentos racionales está estrechamente relacionada con el árbol de Stern-Brocot.
• Árbol Calkin-Wilf

• Brocot, Achille (1861), "Calcul des rouages ​​par approximation, nouvelle méthode", Revue Chronométrique , 3 : 186-194.
• Brocot, Achille (1862), "Calcul des rouages ​​par approximation, nouvelle méthode", https://gallica.bnf.fr/ark:/12148/bpt6k1661912?rk=21459;2
• 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), Combinatoria sobre palabras. Palabras de Christoffel y repeticiones en palabras , CRM Monograph Series, vol.  27, Providence, RI: American Mathematical Society , ISBN 978-0-8218-4480-9, Zbl 1161.68043 

• Aiylam, Dhroova (2013), Secuencias de Stern-Brocot modificadas , arXiv : 1301.6807 , Bibcode : 2013arXiv1301.6807A
• Austin, David, Árboles, dientes y tiempo: Las matemáticas de la relojería , Columna destacada de la AMS
• Bogomolny, Alexander , Brocot-Tree , cut-the-knot , consultado el 3 de septiembre de 2008
• Sloane, NJA , El árbol de Stern-Brocot o de Farey , Enciclopedia en línea de secuencias de enteros.
• Wildberger, Norman (29 de mayo de 2012), MF96: Fracciones y el árbol de Stern-Brocot
• Weisstein, Eric W. , "Árbol de Stern-Brocot" , MathWorld
• Árbol de Stern-Brocot en PlanetMath .
• Código para generar árboles Stern-Brocot en GitHub
• Fracciones infinitas , Numberphile
• Gráficos asombrosos III , Numberphile
• Secuencia OEIS A002487 (serie diatómica de Stern (o secuencia de Stern-Brocot)) .