En teoría de números , el árbol de Stern-Brocot es un árbol binario completo infinito en el que los vértices corresponden uno a uno a los números racionales positivos , cuyos valores están ordenados de izquierda a derecha como en un árbol de búsqueda .
El árbol de Stern-Brocot fue introducido independientemente por Moritz Stern (1858) y Achille Brocot (1861). Stern fue un teórico de números alemán; Brocot fue 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 al encontrar una relación de números suaves cerca de ese 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 puede definirse en términos de fracciones continuas simples o mediantes , y una ruta 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 . Debido a que el árbol contiene cada número racional positivo exactamente una vez, una búsqueda en amplitud del árbol proporciona un método para enumerar 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 un triple de fracciones que consiste en tres fracciones en la misma fila que el vértice, es decir, 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. (Consulte la figura anterior). Las fracciones izquierda y derecha no corresponden a los vértices de la misma fila que el vértice, sino a los vértices de alguna fila anterior. Cada una de estas fracciones puede entenderse como el etiquetado 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 un triple siempre será el mediante del primer y tercer elemento. Por ejemplo, la raíz está asociada con y sus descendientes izquierdo y derecho están asociados con y
El árbol se genera mediante la siguiente regla:
La relación entre padres y descendientes también se puede entender en términos de fracciones continuas. Todo número racional positivo q puede expresarse como una fracción continua de la forma donde k y a 0 son números enteros no negativos, y cada coeficiente posterior a i es un número entero positivo. Esta representación no es única porque pero usar esta equivalencia para reemplazar cada fracción continua que termina en uno por una fracción continua más corta muestra que todo 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 Equivalentemente, este padre se forma disminuyendo el denominador en el término más interno de la fracción continua en 1, y contrayéndose 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 , por lo que su padre en el árbol de Stern-Brocot es el número
A la inversa, cada número q en el árbol de Stern-Brocot tiene exactamente dos hijos: si entonces un hijo es el número representado por la fracción continua mientras que el otro hijo está representado por la fracción continua 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 primera expresión da el hijo izquierdo si k es impar, y el hijo derecho si k es par). Por ejemplo, la representación de fracción continua de 13/9 es [1;2,4] y sus dos hijos son [1;2,5] = 16/11 (el niño correcto) y [1;2,3,2] = 23/16 (el niño de la izquierda).
Está claro que para cada expresión de fracción continua finita uno puede moverse repetidamente a su padre y llegar a la raíz [1;] = 1/1 del árbol en un número infinito de pasos (en pasos 0 + ... + a k − 1 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 en el árbol son los números para los cuales la suma de los coeficientes de fracción continua es d + 1 .
El árbol de Stern-Brocot forma un árbol de búsqueda binario infinito con respecto al ordenamiento habitual de los números racionales. [1] [2] El conjunto de números racionales que descienden de un nodo q está definido por el intervalo abierto ( L q , H q ) donde L q es el ancestro de q que es más pequeño que q y más cercano a él en el árbol (o L q = 0 si q no tiene un ancestro más pequeño) mientras que H q es el ancestro de q que es más grande que q y más cercano a él en el árbol (o H q = +∞ si q no tiene un ancestro más grande).
La ruta 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 manera sencilla utilizando mediantes . Aumente los números racionales no negativos para incluir un valor 1/0 (que representa +∞) que por definición es mayor que todos los demás racionales. El algoritmo de búsqueda binaria procede de la siguiente manera:
La secuencia de valores M calculada por esta búsqueda es exactamente la secuencia de valores en la ruta 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 ( L M , H M ) que representa los descendientes del mediante M . El padre de q en el árbol de Stern-Brocot es el último mediante encontrado 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 a cualquier número racionala/b que no está en la secuencia de mediantes encontrada por el algoritmo anterior, entonces la secuencia de mediantes contiene una aproximación más cercana a x que tiene un denominador como máximo igual a b ; en ese sentido, estos mediantes forman las mejores aproximaciones racionales a x .
El árbol de Stern-Brocot puede definirse directamente en términos de mediantes: el hijo izquierdo de cualquier número q es el mediante de q con su ancestro más pequeño más cercano, y el hijo derecho de q es el mediante de q con su ancestro más grande más cercano. En esta fórmula, q y su ancestro deben tomarse en términos mínimos, y si no hay un ancestro más pequeño o más grande, entonces 0/1 o 1/0 debe usarse respectivamente. Nuevamente, usando 7/5 como ejemplo, su antepasado más pequeño más cercano es 4/3 , entonces su hijo izquierdo es 4 + 7/3 + 5 = 11/8 , y su antepasado más cercano y de mayor tamaño es 3/2 , entonces su hijo correcto 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] que tienen denominador 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 mediantes: la secuencia de Farey de orden n + 1 se forma a partir de la secuencia de Farey de orden n calculando el mediante de cada dos valores consecutivos en la secuencia de Farey de orden n , manteniendo el subconjunto de mediantes que tienen denominador exactamente igual a n + 1 , y colocando estos mediantes entre los dos valores a partir de los cuales se calcularon.
También se puede observar un proceso similar de inserción de un mediante, comenzando con un par diferente de puntos finales de intervalo, para describir 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 y la secuencia de Stern-Brocot de orden i es la secuencia formada al insertar un mediante 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 de contorno 0/1 y 1/0 , en orden numérico.
Por lo tanto, las secuencias de Stern-Brocot difieren de las secuencias de Farey en dos formas: finalmente incluyen todos los racionales positivos, no solo los racionales dentro del intervalo [0,1] , y en el paso n se incluyen todos los mediadores, no solo aquellos con 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 siempre que se alcance un número con denominador mayor que n .
Si todos los racionales están a la misma profundidad en el árbol de Stern-Brocot, entonces
Además, si dos fracciones consecutivas están en un nivel determinado del árbol o por encima de él (en el sentido de que cualquier fracción entre ellas debe estar en un nivel inferior del árbol), entonces [4]
Junto con las definiciones en términos de fracciones continuas y mediantes descritas anteriormente, el árbol de Stern-Brocot también puede definirse como un árbol cartesiano para los números racionales, priorizados por sus denominadores. En otras palabras, es el único árbol binario de búsqueda 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 en este intervalo.
Permutar los vértices en cada nivel del árbol de Stern-Brocot mediante una permutación de inversión de bits produce un árbol diferente, el árbol de Calkin-Wilf , en el que los hijos de cada númeroa/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 binario.
![{\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}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cb12a1ffc802e46e7e3e5dc4ca52c46cd9fb2be0)
![{\displaystyle [a_{0};a_{1},a_{2},\ldots ,a_{k-1},1]=[a_{0};a_{1},a_{2},\ldots ,a_{k-1}+1],}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d646c6e0f1042f84e9ebbff7bf6aa3fb817fa152)
![{\displaystyle [a_{0};a_{1},a_{2},\ldots ,a_{k}-1].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fbae01368e807bec2b6f695b05c0744dacfddc82)
![{\displaystyle {\frac {23}{16}}=1+{\cfrac {1}{2+{\cfrac {1}{3+{\frac {1}{2}}}}}}=[ 1;2,3,2],}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ed9ac14ed7e2ac170a9b51da07c9e781ffd4afac)
![{\displaystyle [1;2,3,1]=[1;2,4]=1+{\cfrac {1}{2+{\frac {1}{4}}}}={\frac {13 }{9}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/84f68e1d0d38af49ed19568c0178366375e0c76e)
![{\displaystyle q=[a_{0};a_{1},a_{2},\ldots ,a_{k}]=[a_{0};a_{1},a_{2},\ldots ,a_{k}-1,1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d00c66a3bb3c48a737aa61741c021069bf4e59a7)
![{\displaystyle \displaystyle [a_{0};a_{1},a_{2},\ldots ,a_{k}+1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/06b087195681925e0da598e3b76e2ebdc224e338)
![{\displaystyle [a_{0};a_{1},a_{2},\ldots ,a_{k}-1,2].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f2f7f955e1a705091134f6139340658d7b911dc4)
![{\displaystyle {\bigl [}{\tfrac {0}{1}},{\tfrac {1}{0}}{\bigr ]},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/552009c7a446c340d4affd01c1cba5a02394e09f)
