Orde schuilt in chaos. Het is de belangrijkste taak van de Ramsey-theorie.
Negentig jaar lang probeerden wiskundigen het te vinden. De vooruitgang was ijzig.
Ze wilden weten wanneer willekeur niet meer werkt. Wanneer structuur verplicht wordt.
De onderwerpen? Grafieken.
Geen grafieken met staven. Netwerken. Punten verbonden door lijnen.
Denk aan luchtvaartroutes. Denk aan vriendschappen. Denk aan moleculen.
Elke grafiek die groot genoeg is, bevat twee dingen.
Een kliek. Een groep waar iedereen iedereen kent.
Of een onafhankelijke set. Een stel mensen die niemand kennen.
R(3,10). Dat is de vraag. Hoe groot moet een sociaal netwerk zijn om drie gemeenschappelijke vrienden of tien vreemden te garanderen?
Wij weten het antwoord niet.
Er bestaan precies minder dan dertig Ramsey-nummers. De rest zijn mysteries.
Daarom gebruiken wiskundigen grenzen. Een val.
Stel je een Star Wars afvalpers voor. 🤖
De ondergrens is één muur. De bovengrens is de andere.
Decennia lang was de kloof enorm.
Toen verscheen Domagoj Bradaä.
Hij werkt bij het Zwitserse Federale Instituut voor Technologie. Vorige maand plaatste hij een bewijs. Het heeft een barrière vernield.
De muren kwamen dichterbij. Sluiten. Heerlijk dichtbij.
Hier is hoe hij het deed.
“Geometrie is iets dat we veel beter begrijpen dan de grafentheorie.” — Marcelo Campos
Bradaä begon niet met chaos. Hij begon met geometrie.
Hij bouwde eerst een gigantische grafiek. Onbuigzaam. Algebraïsch. Gestructureerd.
Waarom?
Omdat geometrie je gratis eigenschappen geeft.
Vervolgens voegde hij er chaos aan toe.
Hij hakte willekeurig zijn grote geometrische grafiek in stukken. Nam een stuk. Enkele slechte knooppunten verwijderd.
Het resultaat?
Grafieken die enorm groeiden. Maar vermeden patronen.
Geen kliekjes. Geen grote onafhankelijke sets.
Gewoon nauwelijks volhouden.
De beste bovengrens? Vast sinds de jaren 1930. Bradaä raakte het bijna aan.
“In een ideale wereld zou ik gewoon zeggen: hier is de grafiek. Dan ben je klaar.” — Domagoj Bradaâ
Jammer dat de wereld niet ideaal is.
Hij bewees dat ze konden bestaan. Hij heeft ze er geen gegeven. Dat is de probabilistische methode. Uitgevonden door Paul Erdäs. Het bestaan door toeval bewijzen.
Brada’s bewijs was goed. Maar het was niet het einde.
Voer AI in.
OpenAI zag het papier. Ik heb het aan hun redeneermodel doorgegeven.
De AI heeft een aanpassing gevonden.
Geen vervanging. Een verscherping.
Het elimineerde het kleine beetje onzekerheid dat nog in Brada’s grenzen zat.
Nu komen de onder- en bovengrenzen overeen met polylogaritmische hiaten.
Eigenlijk niets.
Is het spel voorbij?
Niet helemaal.
“We proberen niet systematisch arXiv-papieren te repareren. We hebben gewoon geluk gehad.” — Mehtaab Sawhney (OpenAI)
De AI heeft het niet allemaal opgelost. Het zette de schroeven van Brada’s werk vast.
Marcelo Campos herinnert ons er graag aan wie het zware werk heeft gedaan. Het concept kwam van de mens. De AI heeft zojuist de randen schoongemaakt.
Nog steeds.
Een AI verbeterde een eeuwenoud wiskundeprobleem. Binnen weken.
Wie wist?
We staan vlak naast de waarheid van de Ramsey-cijfers.
De kloof is dun. Als ijs in april.
Ga erop staan en kijk wat er kapot gaat.
