El árbol de Stern-Brocot y las sucesiones de Farey

Árbol de Stern-Brocot

El árbol de Stern-Brocot es una construcción elegante para representar el conjunto de todas las fracciones positivas. Lo descubrieron de forma independiente el matemático alemán Moritz Stern en 1858 y el relojero francés Achille Brocot en 1861. Sin embargo, algunas fuentes atribuyen el descubrimiento al matemático griego antiguo Eratóstenes.

La construcción empieza en la iteración cero con las dos fracciones

$$\frac{0}{1}, \frac{1}{0}$$

donde cabe señalar que la segunda cantidad no es estrictamente una fracción, pero se puede interpretar como una fracción irreducible que representa el infinito.

En cada iteración posterior, consideramos todas las fracciones adyacentes $\frac{a}{b}$ y $\frac{c}{d}$ e insertamos su mediante  $\frac{a+c}{b+d}$ entre ellas.

Las primeras iteraciones se ven así:

$$\begin{array}{c}{\displaystyle \frac{0}{1}},{\displaystyle \frac{1}{1}},{\displaystyle \frac{1}{0}}\\ {\displaystyle \frac{0}{1}},{\displaystyle \frac{1}{2}},{\displaystyle \frac{1}{1}},{\displaystyle \frac{2}{1}},{\displaystyle \frac{1}{0}}\\ {\displaystyle \frac{0}{1}},{\displaystyle \frac{1}{3}},{\displaystyle \frac{1}{2}},{\displaystyle \frac{2}{3}},{\displaystyle \frac{1}{1}},{\displaystyle \frac{3}{2}},{\displaystyle \frac{2}{1}},{\displaystyle \frac{3}{1}},{\displaystyle \frac{1}{0}}\end{array}$$$$\begin{array}{c} \dfrac{0}{1}, \dfrac{1}{1}, \dfrac{1}{0} \ \dfrac{0}{1}, \dfrac{1}{2}, \dfrac{1}{1}, \dfrac{2}{1}, \dfrac{1}{0} \ \dfrac{0}{1}, \dfrac{1}{3}, \dfrac{1}{2}, \dfrac{2}{3}, \dfrac{1}{1}, \dfrac{3}{2}, \dfrac{2}{1}, \dfrac{3}{1}, \dfrac{1}{0} \end{array}$$

Continuando este proceso hasta el infinito esto cubre todas las fracciones positivas. Además, todas las fracciones serán únicas e irreducibles. Por último, las fracciones también aparecerán en orden creciente.

Antes de demostrar estas propiedades, mostremos realmente una visualización del árbol de Stern-Brocot, más que la representación en lista. Cada fracción del árbol tiene dos hijos. Cada hijo es el mediante del ancestro más cercano a la izquierda y del ancestro más cercano a la derecha.

Demostraciones

Orden. Demostrar el orden es sencillo. Notamos que el mediante de dos fracciones siempre está entre las fracciones

$$\frac{a}{b} \le \frac{a+c}{b+d} \le \frac{c}{d}$$

dado que

$$\frac{a}{b} \le \frac{c}{d}.$$

Las dos desigualdades se pueden mostrar fácilmente reescribiendo las fracciones con denominadores comunes.

Como el orden es creciente en la iteración cero, se mantendrá en cada iteración posterior.

Irreducibilidad. Para demostrar esto mostraremos que para cualesquiera dos fracciones adyacentes $\frac{a}{b}$ y $\frac{c}{d}$ tenemos que

$$bc - ad = 1.$$

Recordemos que una ecuación diofántica con dos variables $ax+by=c$ tiene solución sii $c$ es un múltiplo de $\gcd(a,b)$. En nuestro caso esto implica que $\gcd(a,b) = \gcd(c,d) = 1$, que es lo que queremos mostrar.

Claramente en la iteración cero $bc - ad = 1$. Lo que queda por mostrar es que los mediantes retienen esta propiedad.

Asumamos que nuestras dos fracciones adyacentes cumplen $bc - ad = 1$; después de añadir el mediante a la lista

$$\frac{a}{b}, \frac{a+c}{b+d}, \frac{c}{d}$$

las nuevas expresiones se vuelven

$$\begin{array}{rllll}& {\displaystyle b(a+c)-a(b+d)}& {\displaystyle =1}& & \\ & {\displaystyle c(b+d)-d(a+c)}& {\displaystyle =1}& & \end{array}$$$$\begin{align} b(a+c) - a(b+d) &= 1 \ c(b+d) - d(a+c) &= 1 \end{align}$$

que, usando que $bc-ad=1$, se puede mostrar fácilmente que son verdaderas.

De esto vemos que la propiedad siempre se mantiene y así todas las fracciones son irreducibles.

La presencia de todas las fracciones. Esta demostración está estrechamente relacionada con localizar una fracción en el árbol de Stern-Brocot. Por la propiedad de orden tenemos que el subárbol izquierdo de una fracción contiene solo fracciones menores que la fracción padre, y el subárbol derecho contiene solo fracciones mayores que la fracción padre. Esto significa que podemos buscar una fracción recorriendo el árbol desde la raíz, yendo a la izquierda si el objetivo es menor que la fracción y yendo a la derecha si el objetivo es mayor.

Elijamos una fracción objetivo positiva arbitraria $\frac{x}{y}$. Obviamente está entre $\frac{0}{1}$ y $\frac{1}{0}$, así que la única forma de que la fracción no esté en el árbol es si se necesita un número infinito de pasos para llegar a ella.

Si ese es el caso, en todas las iteraciones tendríamos

$$\frac{a}{b} \lt \frac{x}{y} \lt \frac{c}{d}$$

que (usando el hecho de que un entero $z \gt 0 \iff z \ge 1$) se puede reescribir como

$$\begin{array}{rllll}& {\displaystyle bx-ay}& {\displaystyle \ge 1}& & \\ & {\displaystyle cy-dx}& {\displaystyle \ge 1.}& & \end{array}$$$$\begin{align} bx - ay &\ge 1 \ cy - dx &\ge 1. \end{align}$$

Ahora multipliquemos la primera desigualdad por $c+d$ y la segunda por $a+b$ y sumémoslas para obtener

$$(c+d)(bx - ay) + (a+b)(cy - dx) \ge a+b+c+d.$$

Expandiendo esto y usando la propiedad mostrada antes $bc-ad=1$ obtenemos que

$$x+y \ge a+b+c+d.$$

Y dado que en cada iteración al menos uno de $a,b,c,d$ aumentará, el proceso de búsqueda de la fracción no contendrá más de $x+y$ iteraciones. Esto contradice la suposición de que el camino a $\frac{x}{y}$ era infinito y por lo tanto $\frac{x}{y}$ debe formar parte del árbol.

Algoritmo de construcción del árbol

Para construir cualquier subárbol del árbol de Stern-Brocot, basta conocer el ancestro izquierdo y el derecho. En el primer nivel, los ancestros izquierdo y derecho son $\frac{0}{1}$ y $\frac{1}{0}$ respectivamente. Usando estos, calculamos el mediante y procedemos un nivel más profundo, con el mediante reemplazando al ancestro derecho en el subárbol izquierdo, y viceversa.

Este pseudocódigo intenta construir el árbol infinito entero:

void build(int a = 0, int b = 1, int c = 1, int d = 0, int level = 1) {
    int x = a + c, y = b + d;
 
    ... output the current fraction x/y at the current level in the tree
    
    build(a, b, x, y, level + 1);
    build(x, y, c, d, level + 1);
}

Algoritmo de búsqueda de fracciones

El algoritmo de búsqueda ya se describió en la demostración de que todas las fracciones aparecen en el árbol, pero lo repetiremos aquí. El algoritmo es un algoritmo de búsqueda binaria. Inicialmente estamos en la raíz del árbol y comparamos nuestro objetivo con la fracción actual. Si son iguales hemos terminado y detenemos el proceso. Si nuestro objetivo es menor nos movemos al hijo izquierdo; en caso contrario nos movemos al hijo derecho.

Búsqueda naive

Aquí hay una implementación que devuelve el camino a una fracción dada $\frac{p}{q}$ como una secuencia de caracteres 'L' y 'R', que significan recorrido hacia el hijo izquierdo y el derecho respectivamente. Esta secuencia de caracteres define de forma unívoca todas las fracciones positivas y se llama sistema numérico de Stern-Brocot.

string find(int p, int q) {
    int pL = 0, qL = 1;
    int pR = 1, qR = 0;
    int pM = 1, qM = 1;
    string res;
    while(pM != p || qM != q) {
        if(p * qM < pM * q) {
            res += 'L';
            tie(pR, qR) = {pM, qM};
        } else {
            res += 'R';
            tie(pL, qL) = {pM, qM};
        }
        tie(pM, qM) = pair{pL + pR, qL + qR};
    }
    return res;
}

Los números irracionales en el sistema numérico de Stern-Brocot corresponden a secuencias infinitas de caracteres. A lo largo del camino sin fin hacia el número irracional el algoritmo hallará fracciones reducidas con denominadores gradualmente crecientes que proporcionan aproximaciones cada vez mejores del número irracional. Así, tomando un prefijo de la secuencia infinita se pueden lograr aproximaciones con cualquier precisión deseada. Esta aplicación es importante en relojería, lo que explica por qué se descubrió el árbol en ese dominio.

Nótese que para una fracción $\frac{p}{q}$, la longitud de la secuencia resultante podría ser tan grande como $O(p+q)$, por ejemplo cuando la fracción es de la forma $\frac{p}{1}$. Esto significa que el algoritmo de arriba no debería usarse, a menos que esta sea una complejidad aceptable.

Búsqueda logarítmica

Afortunadamente, es posible mejorar el algoritmo de arriba para garantizar complejidad $O(\log (p+q))$. Para ello debemos notar que si las fracciones frontera actuales son $\frac{p_L}{q_L}$ y $\frac{p_R}{q_R}$, entonces al dar $a$ pasos a la derecha nos movemos a la fracción $\frac{p_L + a p_R}{q_L + a q_R}$, y al dar $a$ pasos a la izquierda, nos movemos a la fracción $\frac{a p_L + p_R}{a q_L + q_R}$.

Por lo tanto, en lugar de dar pasos de L o R uno por uno, podemos dar $k$ pasos en la misma dirección de una vez, después de lo cual cambiaríamos a ir en la otra dirección, y así sucesivamente. De esta manera, podemos hallar el camino a la fracción $\frac{p}{q}$ como su codificación por longitud de racha (run-length encoding).

Como las direcciones alternan de esta manera, siempre sabremos cuál tomar. Así, por conveniencia podemos representar un camino a una fracción $\frac{p}{q}$ como una secuencia de fracciones

$$\frac{p_0}{q_0}, \frac{p_1}{q_1}, \frac{p_2}{q_2}, \dots, \frac{p_n}{q_n}, \frac{p_{n+1}}{q_{n+1}} = \frac{p}{q}$$

tal que $\frac{p_{k-1}}{q_{k-1}}$ y $\frac{p_k}{q_k}$ son las fronteras del intervalo de búsqueda en el $k$-ésimo paso, empezando con $\frac{p_0}{q_0} = \frac{0}{1}$ y $\frac{p_1}{q_1} = \frac{1}{0}$. Entonces, después del $k$-ésimo paso nos movemos a una fracción

$$\frac{p_{k+1}}{q_{k+1}} = \frac{p_{k-1} + a_k p_k}{q_{k-1} + a_k q_k},$$

donde $a_k$ es un número entero positivo. Si uno está familiarizado con las fracciones continuas, reconocería que la secuencia $\frac{p_i}{q_i}$ es la secuencia de las fracciones convergentes de $\frac{p}{q}$ y la secuencia $[a_1; a_2, \dots, a_{n}, 1]$ representa la fracción continua de $\frac{p}{q}$.

Esto permite hallar la codificación por longitud de racha del camino a $\frac{p}{q}$ de la manera que sigue el algoritmo para computar la representación en fracción continua de la fracción $\frac{p}{q}$:

auto find(int p, int q) {
    bool right = true;
    vector<pair<int, char>> res;
    while(q) {
        res.emplace_back(p / q, right ? 'R' : 'L');
        tie(p, q) = pair{q, p % q};
        right ^= 1;
    }
    res.back().first--;
    return res;
}

Sin embargo, este enfoque solo funciona si ya conocemos $\frac{p}{q}$ y queremos hallar su lugar en el árbol de Stern-Brocot.

En la práctica, a menudo ocurre que $\frac{p}{q}$ no se conoce de antemano, pero somos capaces de comprobar para $\frac{x}{y}$ específicos si $\frac{x}{y} < \frac{p}{q}$.

Sabiendo esto, podemos emular la búsqueda en el árbol de Stern-Brocot manteniendo las fronteras actuales $\frac{p_{k-1}}{q_{k-1}}$ y $\frac{p_k}{q_k}$, y hallando cada $a_k$ mediante búsqueda binaria. El algoritmo entonces es un poco más técnico y potencialmente tiene una complejidad de $O(\log^2(x+y))$, a menos que la formulación del problema permita hallar $a_k$ más rápido (por ejemplo, usando floor de alguna expresión conocida).

Sucesión de Farey

La sucesión de Farey de orden $n$ es la secuencia ordenada de fracciones entre $0$ y $1$ cuyos denominadores no superan $n$.

Las sucesiones llevan el nombre del geólogo inglés John Farey, que en 1816 conjeturó que cualquier fracción de una sucesión de Farey es el mediante de sus vecinas. Esto lo demostró algún tiempo después Cauchy, pero de forma independiente de ambos, el matemático Haros había llegado a casi la misma conclusión en 1802.

Las sucesiones de Farey tienen muchas propiedades interesantes por sí mismas, pero la conexión con el árbol de Stern-Brocot es la más obvia. De hecho, las sucesiones de Farey se pueden obtener recortando ramas del árbol.

Del algoritmo para construir el árbol de Stern-Brocot, obtenemos un algoritmo para las sucesiones de Farey. Empezamos con la lista de fracciones $\frac{0}{1}, \frac{1}{0}$. En cada iteración posterior, insertamos el mediante solo si el denominador no supera $n$. En algún momento la lista dejará de cambiar y se habrá hallado la sucesión de Farey deseada.

Longitud de una sucesión de Farey

Una sucesión de Farey de orden $n$ contiene todos los elementos de la sucesión de Farey de orden $n-1$ así como todas las fracciones irreducibles con denominador $n$, pero esto último es simplemente la función totiente $\varphi(n)$. Así que la longitud $L_n$ de la sucesión de Farey de orden $n$ es

$$L_n = L_{n-1} + \varphi(n)$$

o equivalentemente, desenrollando la recursión obtenemos

$$L_n = 1 + \sum_{k=1}^n \varphi(k).$$