Optimality of Wouter van Doorn's Upper Bound for the Mayer-Erd\H{o}s Farey Problem

Resumen Técnico: Optimalidad del Límite Superior de Wouter van Doorn para el Problema de Farey de Mayer–Erdős

Planteamiento del Problema
El artículo aborda una pregunta específica sobre la sucesión de Farey de orden $n$, denotada como $F_n$, que consiste en todas las fracciones reducidas $a/b \in [0, 1]$ con $b \le n$, dispuestas en orden creciente. El objeto central de estudio es el concepto de pares "mal ordenados". Dos fracciones $a/b < c/d$ en $F_n$ se definen como mal ordenadas si sus numeradores aumentan mientras que sus denominadores disminuyen (es decir, $a < c$ y $b > d$).

El artículo investiga la cantidad $f(n)$, definida como el número mínimo de fracciones de Farey estrictamente entre dos fracciones mal ordenadas en $F_n$. Este problema es equivalente al Problema 1005 de Erdős, que busca la constante asintótica $c$ tal que el rango máximo garantizado de fracciones de Farey con orden similar es asintótico a $cn$. El trabajo reciente de Wouter van Doorn estableció el límite superior $f(n) \le n/4 + O(1)$ y conjeturó que este límite es óptimo.

Metodología
La demostración es elemental pero delicada, apoyándose en una combinación de teoría analítica de números y estimaciones combinatorias. La estrategia se divide en establecer un límite inferior coincidente y revisar el límite superior existente.

1. Reducción a Intervalos Elementales:
   Los autores demuestran primero que cualquier par mal ordenado $a/b < c/d$ contiene un "intervalo elemental" específico $I_{a,b} = (a/b, (a+1)/(b-1))$. Por consiguiente, probar el límite inferior para $f(n)$ se reduce a demostrar que para todos los valores válidos de $a, b$, el número de fracciones de Farey en $I_{a,b}$ es al menos $n/4 - o(n)$.

2. Estimaciones Auxiliares:
   La demostración utiliza varios lemas clave:

   • Progresiones Primitivas: Una estimación para el número de soluciones coprimas de ecuaciones diofánticas lineales dentro de un rango.
   • Conteo Uniforme de Farey: Una estimación estándar para el número de fracciones de Farey en un intervalo arbitrario $J$, dada por $\frac{3}{\pi^2}|J|n^2 + O(n \log n)$.
   • Brechas de Farey: Propiedades de las fracciones consecutivas en $F_Q$, específicamente que la longitud de la brecha es $1/ss'$ y la suma de los denominadores supera $Q$.
   • Incrementos de la Función Totiente (El Motor Central): Un lema crítico (Lema 5) relativo a la función $S(x) = \sum_{1 \le e < x} (1 - e/x)\frac{\phi(e)}{e}$. Los autores demuestran que $S(x+y) - S(x) \ge y/4$ para $x \ge 0, y \ge 2$. Esta desigualdad es la fuente de la constante $1/4$.

3. Análisis de Casos para el Límite Inferior:
   Para probar el límite inferior uniforme para $N_n(a, b)$ (el conteo de fracciones en $I_{a,b}$), los autores dividen el análisis basándose en el denominador $b$ y la presencia de racionales "pequeños" dentro del intervalo:

   • Denominadores Pequeños: Si $b$ es pequeño ($b \le n/\log^2 n$), el conteo estándar uniforme de Farey es suficiente.
   • Denominadores Grandes: Si $b$ es grande, el intervalo se analiza en relación con la sucesión de Farey de un orden inferior $Q = \lfloor b^{2/3} \rfloor$.
     • Caso A (Racional Pequeño en el Interior): Si $I_{a,b}$ contiene un racional reducido $h/s$ con $s \le Q$, el conteo se acota por debajo usando una suma ponderada de funciones totientes, aprovechando el Lema 5 para mostrar que la suma es al menos $s/4$.
     • Caso B (Sin Racional Pequeño en el Interior): Si no existe tal racional, $I_{a,b}$ se encuentra dentro de una brecha de $F_Q$. Los autores analizan los extremos de esta brecha, mostrando que el extremo "pequeño" (con denominador $O(b^{1/3})$) permite una estimación de suma totiente similar, produciendo nuevamente el límite de $n/4$.

4. Límite Superior:
   El artículo incluye la construcción de van Doorn para demostrar el límite superior. Al elegir fracciones específicas $L = (2m-1)/4m$ y $R = 2m/(4m-1)$ (donde $m \approx n/4$), los autores muestran que el número de fracciones entre ellas es exactamente $m + O(1) \approx n/4$.

Contribuciones y Resultados Clave

• Teorema Principal: El artículo demuestra que $f(n) = (1/4 + o(1))n$.
• Optimalidad: Este resultado confirma la conjetura de Wouter van Doorn de que su límite superior $f(n) \le n/4 + O(1)$ es óptimo en términos de la constante asintótica.
• Resolución del Problema 1005 de Erdős: El trabajo determina que la constante asintótica solicitada para el Problema 1005 de Erdős es exactamente $c = 1/4$.
• Innovación Técnica: La demostración introduce una estimación de incremento unidimensional robusta para una suma totiente ponderada (Lema 5), que sirve como el motor para derivar la constante $1/4$.

Significado
El artículo resuelve una cuestión de larga data en la teoría de las sucesiones de Farey al determinar el comportamiento asintótico exacto del mínimo espacio entre fracciones mal ordenadas. Al hacer coincidir el límite superior con un límite inferior riguroso, los autores cierran la brecha sobre la constante $c$, estableciéndola como $1/4$. El trabajo se destaca por ser elemental en sus herramientas (evitando maquinaria pesada) pero delicado en su ejecución, particularmente en el manejo uniforme de las sumas de la función totiente a través de diferentes rangos de denominadores. El resultado es validado además por una formalización en Lean 4, asegurando la corrección de la estrategia de la demostración.