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

Technische Samenvatting: Optimaliteit van de bovengrens van Wouter van Doorn voor het Mayer–Erdős Farey-probleem

Probleemstelling
De paper behandelt een specifieke vraag over de Farey-reeks van orde $n$, aangeduid als $F_n$, die bestaat uit alle gereduceerde breuken $a/b \in [0, 1]$ met $b \le n$, gerangschikt in stijgende volgorde. Het centrale object van studie is het concept van "slecht geordende" paren. Twee Farey-breuken $a/b < c/d$ worden gedefinieerd als slecht geordend als hun tellers toenemen terwijl hun noemers afnemen (i.e., $a < c$ en $b > d$).

De paper onderzoekt de grootheid $f(n)$, gedefinieerd als het minimum aantal Farey-breuken strikt tussen twee slecht geordende breuken in $F_n$. Dit probleem is equivalent aan Erdős Probleem 1005, dat vraagt naar de asymptotische constante $c$ waarvoor de grootste gegarandeerde range van vergelijkbaar geordende Farey-breuken asymptotisch gelijk is aan $cn$. Recent werk door Wouter van Doorn heeft de bovengrens $f(n) \le n/4 + O(1)$ vastgesteld en de conjectuur geformuleerd dat deze bovengrens optimaal is.

Methodologie
Het bewijs is elementair maar delicaat, rustend op een combinatie van analytische getaltheorie en combinatorische schattingen. De strategie is verdeeld in het vaststellen van een bijbehorende ondergrens en het beoordelen van de bestaande bovengrens.

1. Reductie naar Elementaire Intervallen:
   De auteurs tonen eerst aan dat elk slecht geordend paar $a/b < c/d$ een specifiek "elementair interval" bevat, $I_{a,b} = (a/b, (a+1)/(b-1))$. Bijgevolg reduceert het bewijzen van de ondergrens voor $f(n)$ tot het aantonen dat voor alle geldige $a, b$, het aantal Farey-breuken in $I_{a,b}$ ten minste $n/4 - o(n)$ is.

2. Auxiliaire Schattingen:
   Het bewijs maakt gebruik van verschillende belangrijke lemma's:

   • Primitieve Progressies: Een schatting voor het aantal coprimale oplossingen van lineaire Diophantische vergelijkingen binnen een bereik.
   • Uniforme Farey-telling: Een standaard schatting voor het aantal Farey-breuken in een willekeurig interval $J$, gegeven door $\frac{3}{\pi^2}|J|n^2 + O(n \log n)$.
   • Farey-gaten: Eigenschappen van opeenvolgende breuken in $F_Q$, specifelijk dat de gatlengte $1/ss'$ is en de som van de noemers groter is dan $Q$.
   • Totient-incrementen (De Kernmotor): Een cruciaal lemma (Lemma 5) betreffende de functie $S(x) = \sum_{1 \le e < x} (1 - e/x)\frac{\phi(e)}{e}$. De auteurs bewijzen dat $S(x+y) - S(x) \ge y/4$ voor $x \ge 0, y \ge 2$. Deze ongelijkheid is de bron van de constante $1/4$.

3. Casusanalyse voor de Ondergrens:
   Om de uniforme ondergrens voor $N_n(a, b)$ (de telling van breuken in $I_{a,b}$) te bewijzen, splitsen de auteurs de analyse op basis van de noemer $b$ en de aanwezigheid van "kleine" rationale getallen binnen het interval:

   • Kleine Noemers: Als $b$ klein is ($b \le n/\log^2 n$), volstaat de standaard uniforme Farey-telling.
   • Grote Noemers: Als $b$ groot is, wordt het interval geanalyseerd relatief aan de Farey-reeks van een lagere orde $Q = \lfloor b^{2/3} \rfloor$.
     • Casus A (Kleine Rationale binnen): Als $I_{a,b}$ een gereduceerde rationale $h/s$ bevat met $s \le Q$, wordt de telling ondergrenzen met behulp van een gewogen som van totient-functies, waarbij gebruik wordt gemaakt van Lemma 5 om aan te tonen dat de som ten minste $s/4$ is.
     • Casus B (Geen Kleine Rationale binnen): Als er geen dergelijke rationale bestaat, ligt $I_{a,b}$ binnen een gat van $F_Q$. De auteurs analyseren de eindpunten van dit gat, waarbij zij aantonen dat het "kleine" eindpunt (met een noemer van $O(b^{1/3})$) een vergelijkbare totient-som schatting mogelijk maakt, wat opnieuw de $n/4$ ondergrens oplevert.

4. Bovengrens:
   De paper bevat de constructie van van Doorn om de bovengrens aan te tonen. Door specifieke breuken $L = (2m-1)/4m$ en $R = 2m/(4m-1)$ te kiezen (waarbij $m \approx n/4$), tonen de auteurs aan dat het aantal breuken tussen hen precies $m + O(1) \approx n/4$ is.

Belangrijkste Bijdragen en Resultaten

• Hoofdstelling: De paper bewijst dat $f(n) = (1/4 + o(1))n$.
• Optimaliteit: Dit resultaat bevestigt de conjectuur van Wouter van Doorn dat zijn bovengrens $f(n) \le n/4 + O(1)$ optimaal is wat betreft de asymptotische constante.
• Resolutie van Erdős Probleem 1005: Het werk bepaalt dat de gevraagde asymptotische constante voor Erdős Probleem 1005 exact $c = 1/4$ is.
• Technische Innovatie: Het bewijs introduceert een robuuste eendimensionale increment-schatting voor een gewogen totient-som (Lemma 5), die dient als de motor voor het afleiden van de $1/4$ constante.

Betekenis
De paper lost een langlopende vraag in de theorie van Farey-reeksen op door het exacte asymptotische gedrag van de minimale afstand tussen slecht geordende breuken vast te leggen. Door de bovengrens te matchen met een rigoureuze ondergrens, sluiten de auteurs de kloof op de constante $c$, en stellen zij deze vast als $1/4$. Het werk wordt gekenmerkt als elementair in zijn instrumenten (het vermijdt zware machinerie) maar delicaat in de uitvoering, met name in de uniforme behandeling van de totient-sommen over verschillende bereiken van noemers. Het resultaat wordt verder gevalideerd door een formalisering in Lean 4, wat de correctheid van de bewijsstrategie waarborgt.