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

Resumo Técnico: Otimalidade do Limite Superior de Wouter van Doorn para o Problema de Mayer–Erdős sobre Sequências de Farey

Enunciado do Problema
O artigo aborda uma questão específica relativa à sequência de Farey de ordem $n$, denotada por $F_n$, que consiste em todas as frações reduzidas $a/b \in [0, 1]$ com $b \le n$, organizadas em ordem crescente. O objeto central de estudo é o conceito de pares "mal ordenados". Dois pares de frações $a/b < c/d$ em $F_n$ são definidos como mal ordenados se seus numeradores aumentam enquanto seus denominadores diminuem (ou seja, $a < c$ e $b > d$).

O artigo investiga a quantidade $f(n)$, definida como o número mínimo de frações de Farey estritamente entre quaisquer dois pares mal ordenados em $F_n$. Este problema é equivalente ao Problema 1005 de Erdős, que pergunta pelo constante assintótico $c$ tal que o maior intervalo garantido de frações de Farey de ordem semelhante é assintótico a $cn$. Enquanto Mayer iniciou a questão e Erdős estabeleceu um limite inferior linear, a constante assintótica precisa permaneceu em aberto. Um trabalho recente de Wouter van Doorn estabeleceu o limite superior $f(n) \le n/4 + O(1)$ e conjecturou que este limite é ótimo.

Metodologia
A prova é elementar, porém delicada, baseando-se em uma combinação de teoria analítica dos números e estimativas combinatórias. A estratégia é dividida entre estabelecer um limite inferior correspondente e revisar o limite superior existente.

1. Redução a Intervalos Elementares:
   Os autores demonstram primeiro que qualquer par mal ordenado $a/b < c/d$ contém um "intervalo elementar" específico $I_{a,b} = (a/b, (a+1)/(b-1))$. Consequentemente, provar o limite inferior para $f(n)$ reduz-se a mostrar que, para todos os $a, b$ válidos, o número de frações de Farey em $I_{a,b}$ é pelo menos $n/4 - o(n)$.

2. Estimativas Auxiliares:
   A prova utiliza vários lemas fundamentais:

   • Progressões Primitivas: Uma estimativa para o número de soluções coprimas de equações diofantinas lineares dentro de um intervalo.
   • Contagem Uniforme de Farey: Uma estimativa padrão para o número de frações de Farey em um intervalo arbitrário $J$, dada por $\frac{3}{\pi^2}|J|n^2 + O(n \log n)$.
   • Gaps de Farey: Propriedades de frações consecutivas em $F_Q$, especificamente que o comprimento do gap é $1/ss'$ e a soma dos denominadores excede $Q$.
   • Incrementos da Função Totiente (O Motor Central): Um lema crítico (Lema 5) referente à função $S(x) = \sum_{1 \le e < x} (1 - e/x)\frac{\phi(e)}{e}$. Os autores provam que $S(x+y) - S(x) \ge y/4$ para $x \ge 0, y \ge 2$. Esta desigualidade é a origem da constante $1/4$.

3. Análise de Casos para o Limite Inferior:
   Para provar o limite inferior uniforme para $N_n(a, b)$ (a contagem de frações em $I_{a,b}$), os autores dividem a análise com base no denominador $b$ e na presença de racionais "pequenos" dentro do intervalo:

   • Denominadores Pequenos: Se $b$ é pequeno ($b \le n/\log^2 n$), a contagem uniforme padrão de Farey é suficiente.
   • Denominadores Grandes: Se $b$ é grande, o intervalo é analisado em relação à sequência de Farey de uma ordem inferior $Q = \lfloor b^{2/3} \rfloor$.
     • Caso A (Racional Pequeno no Interior): Se $I_{a,b}$ contém um racional reduzido $h/s$ com $s \le Q$, a contagem é limitada inferiormente usando uma soma ponderada de funções totientes, aproveitando o Lema 5 para mostrar que a soma é pelo menos $s/4$.
     • Caso B (Nenhum Racional Pequeno no Interior): Se nenhum tal racional existe, $I_{a,b}$ reside dentro de um gap de $F_Q$. Os autores analisam os pontos extremantes deste gap, mostrando que o ponto extremante "menor" (com denominador $O(b^{1/3})$) permite uma estimativa de soma totiente semelhante, novamente resultando no limite de $n/4$.

4. Limite Superior:
   O artigo inclui a construção de van Doorn para demonstrar o limite superior. Ao escolher frações específicas $L = (2m-1)/4m$ e $R = 2m/(4m-1)$ (onde $m \approx n/4$), os autores mostram que o número de frações entre elas é exatamente $m + O(1) \approx n/4$.

Principais Contribuições e Resultados

• Teorema Principal: O artigo prova que $f(n) = (1/4 + o(1))n$.
• Otimalidade: Este resultado confirma a conjectura de Wouter van Doorn de que seu limite superior $f(n) \le n/4 + O(1)$ é ótimo em termos da constante assintótica.
• Resolução do Problema 1005 de Erdős: O trabalho determina que a constante assintótica solicitada para o Problema 1005 de Erdős é exatamente $c = 1/4$.
• Inovação Técnica: A prova introduz uma estimativa de incremento unidimensional robusta para uma soma totiente ponderada (Lema 5), que serve como o motor para derivar a constante $1/4$.

Significância
O artigo resolve uma questão de longa data na teoria das sequências de Farey ao determinar o comportamento assintótico exato do gap mínimo entre frações mal ordenadas. Ao igualar o limite superior com um limite inferior rigoroso, os autores fecham a lacuna sobre a constante $c$, estabelecendo-a como $1/4$. O trabalho é notado por ser elementar em suas ferramentas (evitando maquinário pesado), mas delicado em sua execução, particularmente no tratamento uniforme das somas totientes através de diferentes intervalos de denominadores. O resultado é adicionalmente validado por uma formalização em Lean 4, garantindo a correção da estratégia de prova.