Solution of Erd\H{o}s problem $\# 443$

Stel je een wereld voor waarin getallen niet slechts koude, harde cijfers zijn, maar spelers in een gigantisch, onzichtbaar spel van verstoppertje spelen. Dit is het domein van de getaltheorie, een tak van de wiskunde die gehele getallen behandelt als unieke personages met geheime identiteiten. In dit spel kijken we vaak naar "verzamelingen"—wat gewoon chique woorden zijn voor collecties getallen—die worden gecreëerd door een specifieke regel te volgen. Als je bijvoorbeeld een getal neemt, het vermenigvuldigt met zijn partner (het getal dat samen met het eerste een bepaalde totaal vormt), en alle resultaten opsomt, krijg je een uniek patroon. Wiskundigen houden ervan om te vragen: "Als ik twee verschillende patronen maak met verschillende regels, hoeveel getallen hebben ze dan gemeen?" Het is alsof je vraagt hoeveel woorden in zowel een woordenboek van oude poëzie als in een woordenboek van moderne straattaal voorkomen. De vraag lijkt misschien een puzzel voor een wiskundclub, maar het helpt ons de verborgen architectuur van getallen te begrijpen, waarbij het onthult of patronen zeldzaam, gebruikelijk of volkomen onvoorspelbaar zijn.

Het artikel waar je zo over zult horen, behandelt een specifieke raadsel dat werd voorgelegd door de legendarische wiskundige Paul Erdős. Hij vroeg zich iets af over twee speciale collecties getallen. De eerste collectie wordt gevormd door een getal $m$ te nemen, een kleiner getal $k$ te kiezen (van 1 tot de helft van $m$), en het product $k(m-k)$ te berekenen. De tweede collectie doet precies hetzelfde, maar met een ander getal, $n$. De grote vraag was: naarmate deze getallen enorm groot worden, hoeveel "gemeenschappelijke vrienden" (getallen die in beide lijsten voorkomen) kunnen ze delen? Erdős gokte dat hoewel het aantal gedeelde vrienden zou groeien, het heel langzaam zou groeien—zo langzaam dat voor elke kleine foutmarge die je kiest, de telling uiteindelijk kleiner zou zijn dan een specifieke wiskundige formule die de grootte van de getallen betreft. Hij vroeg ook of dit aantal gedeelde vrienden zonder ooit te stoppen kon groeien, of dat het een plafond zou raken.

De auteur van dit artikel, Stijn Cambie, treedt op als een detective die dit decennia-oude mysterie oplost. Hij bevestigt dat het aantal gedeelde vrienden inderdaad onbegrensd is, wat betekent dat het zo groot kan worden als je wilt als je de juiste getallen $m$ en $n$ kiest. Om dit te bewijzen, gebruikt hij een slimme truc: hij laat zien dat het vinden van een gedeeld getal hetzelfde is als het vinden van een manier om een specifiek verschil van kwadraten in twee kleinere stukjes te breken. Dit verandert het probleem in het tellen van de "delers" (de bouwstenen) van een getal. Omdat we weten dat sommige getallen een enorm aantal delers hebben, bewijst Cambie dat we altijd paren $m$ en $n$ kunnen vinden die een massaal aantal gedeelde vrienden creëren.

Echter, het artikel legt ook een strikte snelheidslimiet op aan deze groei. Cambie demonstreert dat hoewel het aantal gedeelde vrienden enorm kan worden, het ongelooflijk langzaam groeit—zo langzaam dat het past bij de "kleine marge" die Erdős suggereerde. Hij laat zien dat de telling begrensd is door een functie die in essentie "bijna constant" is vergeleken met de grootte van de getallen die erbij betrokken zijn. In gewone taal uitgedrukt: zelfs als je de best mogende getallen kiest om de overlap te maximaliseren, zal het aantal gedeelde vrienden nooit exploderen; het zal altijd een minuscuul fractie blijven van de totale aantallen die betrokken zijn.

Interessant genoeg onthult het artikel een wending in het verhaal: dit probleem was eigenlijk geen nieuwe ontdekking. De auteur merkt op dat een wiskundige genaamd Norbert Hegyvári dit exacte probleem 40 jaar eerder heeft opgelost, maar dat zijn bewijs pas onlangs is gepubliceerd. Dus, terwijl dit artikel een frisse, heldere uitleg biedt en het antwoord bevestigt, behoort de "opgeloste" status van het probleem eigenlijk toe aan dat eerdere, lang verborgen werk. Het artikel gokt niet alleen; het biedt een wiskundig bewijs, waarbij het precies laat zien hoe het aantal gedeelde vrienden zich gedraagt en bevestigt dat het zowel onbegrensd als verrassend klein is in verhouding tot de grootte van de gebruikte getallen.