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

Sintesi Tecnica: Ottimalità del limite superiore di Wouter van Doorn per il problema di Mayer–Erdős sulle sequenze di Farey

Enunciato del Problema
Il saggio affronta una questione specifica riguardante la sequenza di Farey di ordine $n$, indicata con $F_n$, che consiste in tutte le frazioni ridotte $a/b \in [0, 1]$ con $b \le n$, disposte in ordine crescente. L'oggetto centrale di studio è il concetto di coppie "mal ordinate". Due frazioni $a/b < c/d$ in $F_n$ si definiscono mal ordinate se i loro numeratori aumentano mentre i loro denominatori diminuiscono (ovvero $a < c$ e $b > d$).

Il saggio investiga la quantità $f(n)$, definita come il numero minimo di frazioni di Farey strettamente comprese tra due frazioni mal ordinate in $F_n$. Questo problema è equivalente al Problema 1005 di Erdős, che chiede la costante asintotica $c$ tale che il più grande intervallo garantito di frazioni di Farey con ordine simile sia asintotico a $cn$. Il lavoro recente di Wouter van Doorn ha stabilito il limite superiore $f(n) \le n/4 + O(1)$ e ha ipotizzato che tale limite sia ottimale.

Metodologia
La dimostrazione è elementare ma delicata, basata su una combinazione di teoria analitica dei numeri e stime combinatorie. La strategia è divisa nell'instaurazione di un limite inferiore corrispondente e nella revisione dell'esistente limite superiore.

1. Riduzione a Intervalli Elementari:
   Gli autori dimostrano innanzitutto che ogni coppia mal ordinata $a/b < c/d$ contiene un "intervallo elementare" specifico $I_{a,b} = (a/b, (a+1)/(b-1))$. Di conseguenza, dimostrare il limite inferiore per $f(n)$ si riduce a mostrare che, per tutti i validi $a, b$, il numero di frazioni di Farey in $I_{a,b}$ è almeno $n/4 - o(n)$.

2. Stime Ausiliarie:
   La dimostrazione utilizza diverse lami chiave:

• Progressioni Primitive: Una stima per il numero di soluzioni coprime di equazioni diofantiche lineari entro un intervallo.
• Conteggio Uniforme di Farey: Una stima standard per il numero di frazioni di Farey in un arbitrario intervallo $J$, data da $\frac{3}{\pi^2}|J|n^2 + O(n \log n)$.
• Gap di Farey: Proprietà delle frazioni consecutive in $F_Q$, specificamente che la lunghezza del gap è $1/ss'$ e la somma dei denominatori supera $Q$.
• Incrementi della Funzione Totiente (Il Motore Centrale): Una lemma critica (Lemma 5) riguardante la funzione $S(x) = \sum_{1 \le e < x} (1 - e/x)\frac{\phi(e)}{e}$. Gli autori dimostrano che $S(x+y) - S(x) \ge y/4$ per $x \ge 0, y \ge 2$. Questa disuguaglianza è la fonte della costante $1/4$.

3. Analisi dei Casi per il Limite Inferiore:
   Per dimostrare il limite inferiore uniforme per $N_n(a, b)$ (il conteggio delle frazioni in $I_{a,b}$), gli autori suddividono l'analisi in base al denominatore $b$ e alla presenza di razionali "piccoli" all'interno dell'intervallo:

• Denominatori Piccoli: Se $b$ è piccolo ($b \le n/\log^2 n$), il conteggio standard uniforme di Farey è sufficiente.
• Denominatori Grandi: Se $b$ è grande, l'intervallo viene analizzato rispetto alla sequenza di Farey di un ordine inferiore $Q = \lfloor b^{2/3} \rfloor$.
  • Caso A (Razionale Piccolo all'Interno): Se $I_{a,b}$ contiene un razionale ridotto $h/s$ con $s \le Q$, il conteggio è limitato inferiormente usando una somma pesata di funzioni totiente, sfruttando il Lemma 5 per mostrare che la somma è almeno $s/4$.
  • Caso B (Nessun Razionale Piccolo all'Interno): Se non esiste un tale razionale, $I_{a,b}$ giace all'interno di un gap di $F_Q$. Gli autori analizzano gli estremi di questo gap, mostrando che l'estremo "piccolo" (con denominatore $O(b^{1/3})$) permette una simile stima della somma totiente, ottenendo nuovamente il limite $n/4$.

4. Limite Superiore:
   Il saggio include la costruzione di van Doorn per dimostrare il limite superiore. Scegliendo frazioni specifiche $L = (2m-1)/4m$ e $R = 2m/(4m-1)$ (dove $m \approx n/4$), gli autori mostrano che il numero di frazioni tra esse è esattamente $m + O(1) \approx n/4$.

Contributi Principali e Risultati

• Teorema Principale: Il saggio dimostra che $f(n) = (1/4 + o(1))n$.
• Ottimalità: Questo risultato conferma la congettura di Wouter van Doorn secondo cui il suo limite superiore $f(n) \le n/4 + O(1)$ è ottimale in termini di costante asintotica.
• Risoluzione del Problema 1005 di Erdős: Il lavoro determina che la costante asintotica richiesta per il Problema 1005 di Erdős è esattamente $c = 1/4$.
• Innovazione Tecnica: La dimostrazione introduce una robusta stima di incremento monodimensionale per una somma totiente pesata (Lemma 5), che funge da motore per derivare la costante $1/4$.

Significato
Il saggio risolve una questione di lunga data nella teoria delle sequenze di Farey, fissando l'esatto comportamento asintotico del gap minimo tra frazioni mal ordinate. Accoppiando il limite superiore con un rigoroso limite inferiore, gli autori chiudono il divario sulla costante $c$, stabilendola come $1/4$. L'opera è nota per essere elementare nei suoi strumenti (evitando macchinari pesanti) ma delicata nella sua esecuzione, particolarmente nella gestione uniforme delle somme totiente attraverso diversi intervalli di denominatori. Il risultato è ulteriormente validato da una formalizzazione in Lean 4, che garantisce la correttezza della strategia di dimostrazione.