Drie jonge wiskundigen tackelen oude, onopgeloste problemen van Paul Erdös (1)

Inleiding

Paul Erdös (1913-1996) wordt met zijn 1525 papers als een van de grootste, of minstens meest gepassioneerde wiskundigen ooit gezien. Hij stelde dan ook heel veel vragen die hem fascineerden, vele nog steeds onopgelost, nu zelfs bijna 30 jaar na zijn dood. In de recente jaren zijn er drie onderzoekers uit de Lage Landen die zulke probleem hebben opgelost. Voor zover wij weten zijn wij de enigen.

Problemen die gesteld zijn door Erdös zijn automatisch minstens 28 jaar oud. Maar de drie specifieke vragen die onlangs opgelost werden, zijn bijna 50 jaar geleden voor het eerst gesteld. Het gebeurt niet vaak dat problemen die zo lang stand houden toch gekraakt worden. Daarom willen we in drie opeenvolgende verhalen beschrijven hoe zulke ontdekkingen tot stand komen. In deze spinnenweb komt Stijn Cambie aan het woord. Later volgen Wouter van Doorn en Sam Mattheus.

Paul Erdös was niet gelovig. Een bekende uitspraak van hem is dat als God bestond, hij in het bezit zou zijn van `The Book’, een naslagwerk waarin hij de allermooiste bewijzen ooit zou bewaren. Na de dood van Erdös gaven Martin Aigner en Günter Ziegler ter nagedachtenis van hun collega het werk Proofs From THE BOOK uit. Het werd besproken in een bibwijzerbijdrage van UW30/4 (onder de Franse titel Raisonnements Divins).

Hoe en waar de zoektocht voor mij begon

In het verleden had ik (Stijn Cambie) al gewerkt aan problemen van de beroemde wiskundige Paul Erdös. Hij had er een heleboel. Vaak waren ze elegant, maar meestal waren ze frustrerend: het was me nog niet gelukt om er eentje helemaal te doorgronden. Tijdens een conferentie in Boedapest in juli 2024 kwam een van zijn problemen weer eens ter sprake. Het probleem had zijn weg gevonden via bezoekers van een andere recente conferentie. Dit specifieke probleem intrigeerde me, en eerlijk gezegd staat het nog steeds op mijn verlanglijstje voor verder onderzoek. Maar het zette me wel aan het denken en uiteindelijk leidde het me naar de website https://www.erdosproblems.com/ waar een hele verzameling van zijn opgeloste en niet-opgeloste problemen te vinden is. Bij een paar van die open problemen had ik meteen een gevoel van “hier zit iets!”.

Deze intuïtie bleek cruciaal te zijn. Met behulp van een computerprogramma kon ik snel een aantal plausibele beweringen weerleggen. Later, na correspondentie met Thomas Bloom, een wiskundige `research fellow’ verbonden aan de universiteit van Manchester die bekend is voor zijn onderzoek rond bepaalde Erdösproblemen, zijn die resultaten uitgebreid en in een breder onderzoekskader geplaatst. Door verschillende gerelateerde stellingen te bewijzen, konden we begin 2025 eindelijk zeggen dat het probleem 678 na al die jaren volledig opgelost was.

Voor mij is die eerste vonk essentieel, of het nu intuïtie is, interesse of pure fascinatie. Alleen met dat soort nieuwsgierigheid en/of inzicht kun je verder komen dan wat anderen al gedaan hebben! Vervolgens is het een kwestie van volharden en de details onder de knie krijgen, de handen vuil maken met het nodige reken- en puzzelwerk en opzoekingswerk in de literatuur.

Erdös zelf maakt het dan wel niet meer mee, maar samen met medewiskundigen waar ook ter wereld kunnen we er voor zorgen dat we grip krijgen op zijn onopgeloste problemen en vermoedens en dat we er de meest elegante oplossingen voor vinden.

GGD van twee getallenverzamelingen

Bij de voorstelling van probleem 678 starten we met een opmerkelijke ongelijkheid, aangegeven in het kader hieronder. In het linkerlid is er sprake van een ”kleinere verzameling’ (met minder getallen maar ook met kleinere getallen) en in het rechterlid van een ”grotere’ verzameling (met meer getallen maar ook met grotere getallen).

Erdös wilde graag weten of er veel voorbeelden waren van twee verzamelingen opeenvolgende getallen, waarbij het kleinste gemene veelvoud van de kleinere groter was dan het kleinste gemene veelvoud van de grotere verzameling.

In dit probleem spelen priemgetallen een belangrijke rol. Als de getallen in de kleinste set minder gemeenschappelijke priemfactoren hebben dan de getallen in de grootste set, kan het kleinste gemene veelvoud toch groter zijn. Denk bijvoorbeeld aan de getallen 5 en 7 die het getal 35 als kleinste gemene veelvoud hebben en de grotere getallen 6 en 8 die 24 als kleinste gemene veelvoud hebben. De getallen 5 en 7 hebben geen gemeenschappelijke priemfactor en de getallen 6 en 8 hebben 2 als gemeenschappelijke priemfactor. Via de formule \(\textrm{kgv} (a,b)=\frac{a\cdot b}{\textrm{ggd} (a,b)}\) zie je makkelijk in dat het kleinste gemene veelvoud van twee getallen kleiner wordt als de grootste gemene deler toeneemt.

In dit voorbeeld heeft de kleine verzameling 11 elementen en de grote verzameling 13 elementen. In de kleine verzameling zijn er \(5=\left \lfloor \frac{11}{2} \right \rfloor\) tweevouden en in de grote verzameling zijn er \(7=\left \lceil \frac{13}{2} \right \rceil\) tweevouden. Bij de eerste breuk ronden we naar onder af omdat het rijtje met een oneven getal begint en bij het tweede rijtje naar boven omdat het rijtje met een even getal begint. Zo ook vinden we dat bij het eerste rijtje er \(3=\left \lfloor \frac{11}{3} \right \rfloor\) drievouden zijn en er in het tweede rijtje \(5=\left \lceil \frac{13}{3} \right \rceil\) drievouden zijn. En ook bij de veelvouden van 5 (resp. de veelvouden van 7) vind je er meer in de verzameling van 13 dan in de verzameling van 11.

In de verzameling met 13 elementen zijn er dus meer gemeenschappelijke priemfactoren dan in de verzameling met 11 elementen. De getallen 11 en 13 zijn dus waardevolle kandidaten voor de lengte van de twee rijtjes waar Erdös naar zocht.

Uiteindelijk heb ik oneindig veel van deze voorbeelden kunnen construeren. Hiervoor moesten startwaardes van de rijtjes gekozen worden die dichtbij of net ver van een veelvoud van bepaalde priemgetallen zitten. De berekening van de ideale startwaarden heb ik gemaakt met behulp van de Chinese reststelling, een basistool in de getaltheorie.

Heel wat andere problemen van Paul Erdös hebben te maken met delers van getallen. In de volgende paragrafen stel ik er nog twee voor die mijn aandacht trokken en waarin ik vooruitgang boekte.

Dichtheden van natuurlijke getallen

Probleem 692 gaat over een bepaalde dichtheid \(\delta_1(n,m)\) van natuurlijke getallen. Hiermee bedoelen we de kans dat een natuurlijk getal precies één deler (niet meer en ook niet minder) heeft in de verzameling \(\{n+1,n+2, \dots ,m-1\}\).

Als we bijvoorbeeld \(\delta_1 (3,5)\) willen berekenen zoeken we de kans dat een willekeurig natuurlijk getal \(x\) deelbaar is door 4 of dat 4 een deler is van een willekeurig getal \(x\) (in symbolen: \(4|x\)). Er zit immers maar één natuurlijk getal tussen 3 en 5.

\(\delta_1 (3,5)=\textrm{P}(4|x)=\frac{1}{4}.\)

Erdös vroeg zich af of de waarden van \(\delta_1(n,m)\) zich niet heel specifiek moesten gedragen wanneer je \(n\) vastneemt en wanneer \(m\) steeds groter wordt.

Het vermoeden was dat bij kleine breedten van het delersinterval \(m-n\) de kans klein was dat een willekeurig natuurlijk getal \(x\) precies één deler zou hebben in de verzameling \(\{n+1,n+2, \dots ,m-1\}\). Als de breedte \(m-n\) groter werd zou deze kans op precies één deler in deze verzameling groeien. En als deze breedte nog groter werd zou deze kans weer afnemen omdat het dan waarschijnlijker werd dat \(x\) twee of meer delers in deze verzameling zou hebben.

Zouden de kansen dus eerst stijgen en daarna weer dalen in functie van \(m\)? Het antwoord on deze vraag is negatief. Dit blijkt uit het volgende voorbeeld, waarvan de berekeningen volgen.

Berekeningen van dichtheden

Het berekeningen van dichtheden kan een hele klus zijn. Om dit te illustreren voeren we hieronder enkele berekeningen uit.

Voor de berekening van \(\delta_1(3,6)\) zoeken we de kans dat een willekeurig natuurlijk getal deelbaar is door \(4\) of deelbaar is door \(5\) maar niet door \(4 \cdot 5\).

\(\begin{align*}
\delta_1(3,6)&=\textrm{P}(4|x)+\textrm{P}(5|x)-2\cdot \textrm{P}(20|x) \\
&=\frac{1}{4}+\frac{1}{5}-2\cdot \frac{1}{20}\\
&=\frac{7}{20}
\end{align*}\)

De kans dat 20 een deler is van \(x\) is zowel meegerekend in \(\textrm{P}(4|x)\) als in \(\textrm{P}(5|x)\). Als we de getallen die zowel een veelvoud van \(4\) zijn als van \(5\) niet willen laten meetellen, moet de kans \(\textrm{P}(20|x)\) hier nog twee keer van afgetrokken worden. Dit is een voorbeeld van het inclusie-exclusie-principe.

Voor de berekening van \(\delta_1(3,7)\) zoeken we de kans dat een willekeurig natuurlijk getal deelbaar is door \(4\), \(5\) of \(6\) maar niet door \(4 \cdot 5\), \(4 \cdot 6\) of \(5 \cdot 6\) en ook niet door \(4\cdot 5 \cdot 6\).

\(\begin{align*}
\delta_1(3,7)&=\textrm{P}(4|x)+\textrm{P}(5|x)+\textrm{P}(6|x) \\
&\quad -2\cdot \textrm{P}(20|x)-2\cdot \textrm{P}(12|x)-2\cdot \textrm{P}(30|x) \\
&\quad +3 \cdot \textrm{P}(60|x) \\
&=\frac{1}{4}+\frac{1}{5}+\frac{1}{6}- \frac{2}{20}-\frac{2}{12}-\frac{2}{30}+\frac{3}{60}\\
&=\frac{1}{3}
\end{align*}\)

Het inclusie-exclusie-principe wordt bij deze berekening een beetje ingewikkelder. De kans dat een natuurlijk getal deelbaar is door precies twee van de drie getallen (\(4\), \(5\) of \(6\)) is duidelijk niet meegerekend. Dat merk je aan de aftrekkingen van termen met coëfficiënt 2. De kans dat een natuurlijk getal \(x\) deelbaar is door \(4\), \(5\) en \(6\) telt drie keer in positieve zin mee via \(\textrm{P}(4|x)+\textrm{P}(5|x)+\textrm{P}(6|x)\), zes keer in negatieve zin via \(-2\cdot \textrm{P}(20|x)-2\cdot \textrm{P}(12|x)-2\cdot \textrm{P}(30|x)\) en drie keer in positieve zin via \(3 \cdot\textrm{P}(60|x)\). Zo zie je dat de getallen die zowel deelbaar zijn door \(4\), door \(5\) als door \(6\) ook uitgesloten zijn in deze berekening.

Voor de berekening van \(\delta_1(3,8)\) wordt het inclusie-exclusie-principe te moeilijk. Een efficiëntere manier om deze kans te berekenen is via recursie. Deze aanpak steunt op de dichtheid van natuurlijke getallen die geen enkele deler in de verzameling \(\{n+1,n+2, \dots ,m-1\}\) hebben. We noteren deze kans als \(\delta_0(n,m)\).

Zonder verdere uitleg vermelden we dat

\(\begin{align*}
\delta_1(3,8)&=\frac{6}{7} \cdot \delta_1(3,7)+\frac{1}{7} \cdot \delta_0(3,7) \\
&=\frac{6}{7} \cdot \frac{1}{3}+\frac{1}{7} \cdot \frac{8}{15} \\
&= \frac{38}{105}.
\end{align*}\)

Daar \(\frac 14 < \frac {7}{20} > \frac 13 < \frac{38}{105}\) werd niet voldaan aan het verwachte gedrag bij \(n=3.\)

In mijn onderzoek heb ik aangetoond dat er voor iedere \(n>1\) gelijkaardige onregelmatigheden voorkomen, door een algemeen patroon te herkennen en dit te bewijzen.

Besluit

Terwijl het tegenvoorbeeld met \(n=3\) hierboven voldoende heeft aangetoond dat \(\delta_1(n,m)\) niet eerst stijgt en daarna daalt als \(m\) toeneemt, is hiermee de vraag van Erdös niet helemaal opgelost. Misschien is het vermoeden wel waar voor specifieke waarden van \(n\). En inderdaad, voor \(n=1\) ontdekte ik dat de uitspraak over het stijgen en het dalen van de dichtheid van \(\delta_1(n,m)\) wel correct is.

Dalende rij van grootste priemfactoren

In probleem 648 bekijken we rijtjes van opeenvolgende natuurlijke getallen waarin kleinere getallen een grotere grootste priemfactor hebben dan grote getallen.

Deze omschrijving is best wel ingewikkeld. Daarom geef ik hieronder een voorbeeld van een rijtje met vier opeenvolgende getallen.

Als we een lang rijtje willen hebben dat aan deze eigenschap voldoet, zal het grootste getal in de rij best groot moeten zijn. Erdös vroeg zich af hoe lang dit dan wel was.

Je zou de vraag ook op een andere manier kunnen formuleren. Als het grootste getal van het rijtje ten hoogste gelijk is aan \(n\), hoeveel getallen heeft dan het langste rijtje dat aan deze voorwaarde voldoet? Voor grote waarden van \(n\) heb ik kunnen aantonen dat de lengte van het langste rijtje ergens tussen \(2 \sqrt{\frac{n}{\ln n}}\) en \(2 \sqrt{\frac{2n}{\ln n}}\) ligt.

Hoe kom je nu uit bij zulk een eigenaardige formule? Laat ons beginnen met een eenvoudigere afschatting, de bovengrens \(2 \sqrt n\), te bewijzen.

Hiervoor steunen we op een elementair en belangrijk inzicht. Ieder getal \(a\) in de rij, is gelijk is aan het product van zijn grootste priemdeler \(p\) en een ander natuurlijk getal \(q\). Nu zal het gegeven dat \(a=q \cdot p\) begrensd is door \(n\) betekenen dat ofwel \(p \le \sqrt{n}\) ofwel \(q \le \sqrt{n}\). In het eerste geval zijn er hooguit \(\sqrt{n}\) mogelijkheden voor \(p\) want de waarden van \(p\) mogen niet gelijk zijn. In het tweede geval zijn er hooguit \(\sqrt{n}\) mogelijkheden voor \(q\) en dus ook hooguit \(\sqrt{n}\) mogelijkheden voor \(p\). In totaal zijn er dus ten hoogste \(2 \sqrt{n}\) mogelijkheden voor \(p\). Dit is ook de bovengrens voor de lengte van het gezochte rijtje.

Ik zal niet in detail gaan voor de exact bepaalde bovengrens, maar het tweede belangrijke ingrediënt van het onderzoek was de basisformule voor de spreiding van de priemgetallen, rond 1896 gelijktijdig maar onafhankelijk van elkaar bewezen door de Franse wiskundige Jacques Hadamard en onze landgenoot Charles-Jean de La Vallée-Poussin. Zij toonden aan dat voor grote waarden \(n\) het aantal priemgetallen kleiner dan \(n\) ongeveer gelijk is aan \(\frac{n}{\ln n}\).

Het exacte bewijs is ondertussen nagekeken door twee referees (anonieme collega-wiskundigen) die, na waardevolle feedback gegeven te hebben, het licht op groen hebben gezet voor publicatie in het tijdschrift Proceedings of the American Mathematical Society. Dat nakijken is de manier om bevestigd te krijgen dat de uitspraken ook correct zijn.

Niettegenstaande deze vraag nu als opgelost staat aangeduid op www.erdosproblems.com is dit weliswaar een subjectieve uitspraak. De ondergrens en de bovengrens voor de lengte van dit langste rijtje kunnen altijd nog scherper gesteld worden.

Bronnen

Cambie, S. (z.d.).On Erdös problem #648.  Geaccepteerd in Proceedings of the American Mathematical Society, https://doi.org/10.1090/proc/17279 en in arXiv,  https://arxiv.org/abs/2503.22691 .

Erdös Problems,  https://www.erdosproblems.com/, geraadpleegd op 2025-05-02.