Resolution of two conjectures by Erd\H{o}s and Hall concerning separable numbers

Probleemstelling
Dit artikel behandelt twee conjecturen die door Erdős en Hall zijn voorgesteld met betrekking tot "separeerbare getallen" en "verstrengelde paren". Volgens hun terminologie vormen twee positieve gehele getallen $m$ en $n$ een verstrengeld paar als, tussen elke twee opeenvolgende delers van $n$ (beide groter dan 1), een deler van $m$ bestaat, en omgekeerd. Een geheel getal wordt gedefinieerd als separeerbaar als het tot zo'n paar behoort.

De auteurs richten zich op twee specifieke open problemen:

1. Dichtheid van separeerbare machten van twee: Erdős en Hall veronderstelden dat $2^k$ separeerbaar is voor bijna alle $k$. Zij merkten ook de moeilijkheid op om te bepalen of de tel functie $A(x)$ (het aantal separeerbare gehele getallen tot $x$) voldoet aan $A(x) = o(x)$.
2. Verstrengelde producten van priemgetallen: Erdős en Hall veronderstelden dat, als $k$ voldoende groot is, er geen verstrengeld paar $(m, n)$ bestaat zodanig dat hun product $mn$ gelijk is aan $P_k$, het product van de eerste $k$ priemgetallen.

Methodologie
De auteurs maken gebruik van een combinatie van combinatorische getaltheorie, deleranalyse en resultaten over priemgaten om deze conjecturen op te lossen.

• Deler telling en pariteit: Het artikel begint met het vaststellen van Lemma 1, dat het aantal delers $\tau(n)$ van twee verstrengelde getallen relateert. Specifiek, als $d_2(n) < d_2(m)$, dan geldt $\tau(m) = \tau(n)$ als $n < m$, en $\tau(m) = \tau(n) - 1$ als $n > m$. Dit lemma is cruciaal voor het afleiden van contradicties met betrekking tot de structuur van potentiële verstrengelde partners.
• Weerspreking van de conjectuur over $2^k$:
  • Om te tonen dat $2^k$ niet separeerbaar is voor een positieve onderdichtheid van $k$, analyseren de auteurs de beperkingen op de delers van een hypothetische partner $m$. Door gevallen te onderzoeken waarin $\tau(m)$ oneven of even is en modulair rekenen te gebruiken ($k \equiv 1, 2, 9, 10 \pmod{12}$), tonen zij aan dat elke dergelijke $m$ noodzakelijkerwijs delers zou bezitten die de verstrengelingsvoorwaarde schenden (bijvoorbeeld het creëren van gaten tussen opeenvolgende machten van 2 die niet kunnen worden opgevuld).
  • Om te tonen dat $2^k$ wel separeerbaar is voor een positieve onderdichtheid van $k$, definiëren de auteurs een verzameling $S$ van gehele getallen met "goed verspreide" delers. Met behulp van Lemma 4 (een resultaat over de verdeling van delers in intervallen) en Lemma 3 (resultaten over priemgaten) bewijzen zij dat de verzameling $S$ meer dan de helft van alle positieve gehele getallen bevat. Zij construeren vervolgens een specifieke verstrengelde partner $m$ voor $n=2^k$ telkens wanneer $k$ behoort tot een geschaalde versie van $S$ ($2^t S$), waarmee het bestaan van separeerbare machten van twee voor een positieve dichtheid van exponenten wordt bewezen.
• Bevestiging van de productconjectuur:
  • Voor de tweede conjectuur analyseren de auteurs de verdeling van priemfactoren tussen $m$ en $n$ wanneer $mn = P_k$. Door iteratief kleine priemfactoren toe te wijzen aan $m$ en $n$ op basis van de verstrengelingsvereiste, tonen zij aan dat voor $k > 8$ de beperkingen een contradictie forceren waarbij $m$ delers moet hebben die $n$ niet kan accommoderen (specifiek met betrekking tot delers zoals 23 en 26 versus het onvermogen van $n$ om een veelvoud te zijn van 24 of 25).

Belangrijkste bijdragen en resultaten
Het artikel biedt definitieve oplossingen voor de twee conjecturen:

1. Weerspreking van de "Bijna Alle" conjectuur: De auteurs bewijzen dat de onderdichtheid van $k$ waarvoor $2^k$ separeerbaar is positief is, maar cruciaal is ook dat de onderdichtheid van $k$ waarvoor $2^k$ niet separeerbaar is positief is.

   • Stelling 2: Voor alle $k > 2$ met $k \equiv 1, 2, 9, 10 \pmod{12}$ is $2^k$ niet separeerbaar.
   • Stelling 6: Als $k \in 2^t S$ (waarbij $S$ de verzameling is van gehele getallen met goed verdeelde delers), dan is $2^k$ separeerbaar. De onderdichtheid van dergelijke $k$ is ten minste $1/2^{t+1}$.
   • Betekenis: Dit weerlegt de conjectuur dat $2^k$ separeerbaar is voor bijna alle $k$, en toont aan dat niet-separeerbare machten van twee frequent genoeg zijn om een positieve onderdichtheid te hebben.

2. Bevestiging van de productconjectuur:

   • Stelling 9: Als $(m, n)$ een verstrengeld paar is zodanig dat $mn = P_k$ (het product van de eerste $k$ priemgetallen), dan geldt $k \le 8$.
   • Betekenis: Dit bevestigt de Erdős-Hall conjectuur dat voor grote $k$ geen dergelijk verstrengeld paar bestaat. De auteurs merken expliciet op dat voor even $k \le 8$ dergelijke paren wel bestaan, maar dat zij ophouden te bestaan boven deze drempel.

Betekenis
Het artikel lost twee langdurige open problemen op in de theorie van separeerbare getallen. Door te bewijzen dat de verzameling van niet-separeerbare machten van twee een positieve onderdichtheid heeft, verduidelijken de auteurs de verdeling van separeerbare getallen, en tonen zij aan dat de eigenschap niet zo alomtegenwoordig is als eerder verondersteld. Bovendien, door een strikte bovengrens ($k \le 8$) vast te stellen voor verstrengelde paren gevormd door het product van de eerste $k$ priemgetallen, legt het artikel de structurele beperkingen van dergelijke paren in relatie tot primoriale vast. De auteurs merken ook op dat hun resultaten zijn geverifieerd met behulp van de Lean bewijsassistent.