Introductie
Half oktober, Justin Gilmer vloog van Californië naar New York om de bruiloft van een vriend bij te wonen. Terwijl hij aan de oostkust was, bezocht hij zijn voormalige adviseur, Michaël Saks, een wiskundige aan de Rutgers University, waar Gilmer zeven jaar eerder was gepromoveerd.
Saks en Gilmer praatten bij tijdens de lunch, maar ze praatten niet over wiskunde. Sterker nog, Gilmer had niet serieus nagedacht over wiskunde sinds hij in 2015 bij Rutgers afstudeerde. Op dat moment had hij besloten dat hij geen carrière in de academische wereld wilde en in plaats daarvan zichzelf begon te leren programmeren. Terwijl hij en Saks aten, vertelde Gilmer zijn oude mentor over zijn baan bij Google, waar hij werkt aan machine learning en kunstmatige intelligentie.
Het was zonnig op de dag dat Gilmer Rutgers bezocht. Terwijl hij rondliep, herinnerde hij zich hoe hij in 2013 het grootste deel van een jaar over dezelfde campuspaden had gelopen, denkend aan een probleem dat het vermoeden van vakbondssluiting wordt genoemd. Het was een fixatie geweest, zij het een vruchteloze: ondanks al zijn inspanningen was Gilmer er alleen maar in geslaagd zichzelf te leren waarom het ogenschijnlijk simpele probleem over getallenreeksen zo moeilijk op te lossen was.
“Ik denk dat veel mensen nadenken over het probleem totdat ze er zeker van zijn dat ze begrijpen waarom het moeilijk is. Ik heb er waarschijnlijk meer tijd aan besteed dan de meeste mensen,' zei Gilmer.
Na zijn bezoek in oktober gebeurde er iets onverwachts: hij kreeg een nieuw idee. Gilmer begon na te denken over manieren om technieken uit de informatietheorie toe te passen om het union-closed vermoeden op te lossen. Hij streefde het idee een maand lang na, telkens in de verwachting dat het zou mislukken. Maar in plaats daarvan bleef het pad naar een bewijs zich openen. Eindelijk, op 16 november hij plaatste een eerste resultaat in zijn soort dat brengt wiskundigen een eind op weg om het volledige vermoeden te bewijzen.
Het papier veroorzaakte een golf van vervolgwerk. Wiskundigen van onder meer de Universiteit van Oxford, het Massachusetts Institute of Technology en het Institute for Advanced Study bouwden al snel voort op de nieuwe methoden van Gilmer. Maar voordat ze dat deden, stelden ze zelf een vraag: wie is deze man eigenlijk?
Halfvol
Het union-closed vermoeden gaat over verzamelingen getallen die verzamelingen worden genoemd, zoals {1, 2} en {2, 3, 4}. U kunt bewerkingen op sets uitvoeren, inclusief hun unie nemen, wat betekent dat u ze combineert. De vereniging van {1, 2} en {2, 3, 4} is bijvoorbeeld {1, 2, 3, 4}.
Een verzameling of familie van verzamelingen wordt als "union-closed" beschouwd als de vereniging van twee willekeurige verzamelingen in de familie gelijk is aan een bestaande verzameling in de familie. Beschouw bijvoorbeeld deze familie van vier sets:
{1}, {1, 2}, {2, 3, 4}, {1, 2, 3, 4}.
Combineer elk paar en je krijgt een set die al in de familie zit, waardoor de familievereniging gesloten is.
Wiskundigen praatten al in de jaren zestig over versies van het door de vakbond gesloten vermoeden, maar het kreeg zijn eerste formele verklaring in 1960, in een paper van Peter Frankl, een Hongaarse wiskundige die in de jaren tachtig naar Japan emigreerde en straatoptredens tot zijn bezigheden rekent.
Frankl vermoedde dat als een familie van sets gesloten is, deze ten minste één element (of nummer) moet hebben dat in ten minste de helft van de sets voorkomt. Het was om twee redenen een natuurlijke drempel.
Ten eerste zijn er direct beschikbare voorbeelden van vakbondsgesloten families waarin alle elementen voorkomen in precies 50% van de sets. Zoals alle verschillende sets die je kunt maken van bijvoorbeeld de cijfers 1 tot en met 10. Er zijn 1,024 van dergelijke sets, die een gesloten familie vormen, en elk van de 10 elementen komt voor in 512 daarvan. En ten tweede, op het moment dat Frankl het vermoeden uitte, had niemand ooit een voorbeeld gegeven van een door een vakbond gesloten gezin waarin het vermoeden niet klopte.
Dus 50% leek de juiste voorspelling.
Dat betekende niet dat het gemakkelijk te bewijzen was. In de jaren na het artikel van Frankl zijn er weinig resultaten geboekt. Voorafgaand aan het werk van Gilmer slaagden die kranten er alleen in om drempels vast te stellen die varieerden met het aantal sets in de familie (in tegenstelling tot dezelfde drempel van 50% voor setfamilies van elke omvang).
"Het voelt alsof het gemakkelijk zou moeten zijn, en het is vergelijkbaar met veel problemen die gemakkelijk zijn, maar het heeft aanvallen weerstaan," zei Wil Sawin van de Columbia-universiteit.
Het gebrek aan vooruitgang weerspiegelde zowel de lastige aard van het probleem als het feit dat veel wiskundigen er liever niet over nadachten; ze waren bang dat ze jaren van hun carrière zouden verliezen door een verleidelijk probleem na te jagen dat onmogelijk op te lossen was. Gilmer herinnert zich een dag in 2013 toen hij naar het kantoor van Saks ging en het vermoeden van een vakbond ter sprake bracht. Zijn adviseur - die in het verleden zelf met het probleem had geworsteld - gooide hem bijna de kamer uit.
"Mike zei: 'Justin, je gaat me weer aan het denken zetten over dit probleem en dat wil ik niet doen'", zei Gilmer.
Een inzicht van onzekerheid
Na zijn bezoek aan Rutgers rolde Gilmer het probleem door zijn hoofd en probeerde te begrijpen waarom het zo moeilijk was. Hij spoorde zichzelf aan met een fundamenteel feit: als je een gezin hebt van 100 sets, zijn er 4,950 verschillende manieren om er twee te kiezen en hun verbintenis te nemen. Toen vroeg hij zich af: hoe is het mogelijk dat 4,950 verschillende vakbonden teruggaan naar slechts 100 sets als er geen enkel element in die vakbonden verschijnt met enige frequentie?
Zelfs op dat moment was hij op weg naar een bewijs, al wist hij dat nog niet. Technieken uit de informatietheorie, die een rigoureuze manier van denken bieden over wat je kunt verwachten als je willekeurig een paar objecten trekt, zouden hem daarheen brengen.
Informatietheorie ontwikkeld in de eerste helft van de 20e eeuw, het beroemdst met Claude Shannon's paper uit 1948, "Een wiskundige communicatietheorie.” Het artikel bood een precieze manier om de hoeveelheid informatie te berekenen die nodig is om een bericht te verzenden, gebaseerd op de hoeveelheid onzekerheid over wat het bericht precies zou zeggen. Deze link - tussen informatie en onzekerheid - was Shannons opmerkelijke, fundamentele inzicht.
Om een speelgoedvoorbeeld te nemen, stel je voor dat ik vijf keer een munt opgooi en de resulterende reeks naar je stuur. Als het een normale munt is, zijn er vijf bits aan informatie nodig om te verzenden. Maar als het een geladen munt is - laten we zeggen, 99% kans om op kop te landen - kost het veel minder. We kunnen bijvoorbeeld van tevoren afspreken dat ik je een 1 (een enkel stukje informatie) stuur als de geladen munt alle vijf keer op kop valt, wat zeer waarschijnlijk zal gebeuren. Er is meer verrassing in de uitkomst van een eerlijke coinflip dan in een bevooroordeelde, en dus meer informatie.
Hetzelfde denken is van toepassing op de informatie in cijferreeksen. Als ik een familie van unie-gesloten sets heb - laten we zeggen de 1,024 sets gemaakt van de nummers 1 tot 10 - zou ik twee sets willekeurig kunnen kiezen. Dan kan ik de elementen van elke set aan u communiceren. De hoeveelheid informatie die nodig is om dat bericht te verzenden, weerspiegelt de hoeveelheid onzekerheid over wat die elementen zijn: er is bijvoorbeeld 50% kans dat het eerste element in de eerste set een 1 is (omdat 1 voorkomt in de helft van de sets in de familie), net zoals er 50% kans is dat het eerste resultaat in een reeks eerlijke muntopgooien kop is.
Informatietheorie komt vaak voor in combinatoriek, een gebied van de wiskunde dat zich bezighoudt met het tellen van objecten, wat Gilmer als afgestudeerde student had bestudeerd. Maar toen hij terug naar huis vloog, naar Californië, maakte hij zich zorgen dat de manier waarop hij dacht de informatietheorie te verbinden met het vermoeden van een gesloten vakbond, het naïeve inzicht van een amateur was: werkende wiskundigen waren dit glimmende object zeker eerder tegengekomen en herkenden het als dwaas goud .
"Eerlijk gezegd ben ik een beetje verbaasd dat niemand hier eerder aan heeft gedacht", zei Gilmer. "Maar misschien moet ik niet verbaasd zijn, want ik had er zelf een jaar over nagedacht en ik kende de informatietheorie."
Eerder wel dan niet
Gilmer werkte 's nachts aan het probleem, nadat hij klaar was met zijn werk bij Google, en in het weekend gedurende de tweede helft van oktober en begin november. Hij werd aangemoedigd door ideeën die een groep wiskundigen jaren eerder had onderzocht in een open samenwerking op de blog van een prominente wiskundige genaamd Tim Gowers. Hij werkte ook met een leerboek aan zijn zijde, zodat hij formules kon opzoeken die hij was vergeten.
“Je zou denken dat iemand die met een mooi resultaat komt, hoofdstuk 2 van Elementen van informatietheorie, maar dat deed ik, 'zei Gilmer.
Gilmer's strategie was om zich een door een vakbond gesloten gezin voor te stellen waarin geen enkel element in zelfs maar 1% van alle sets voorkwam - een tegenvoorbeeld dat, als het echt zou bestaan, het vermoeden van Frankl zou vervalsen.
Laten we zeggen dat je twee sets, A en B, willekeurig uit deze familie kiest en de elementen die in die sets zouden kunnen zitten, een voor een bekijkt. Vraag nu: Wat is de kans dat set A het getal 1 bevat? En stel B? Aangezien elk element iets minder dan 1% kans heeft om in een bepaalde set te verschijnen, zou je niet verwachten dat A of B 1 bevat. doet.
Denk vervolgens na over de kans dat de vereniging van A en B 1 bevat. Het is nog steeds onwaarschijnlijk, maar het is waarschijnlijker dan de kans dat het voorkomt in een van de individuele sets. Het is de som van de kans dat het voorkomt in A en de kans dat het voorkomt in B minus de kans dat het voorkomt in beide. Dus misschien iets minder dan 2%.
Dit is nog steeds laag, maar het komt dichter bij een 50-50 voorstel. Dat betekent dat er meer informatie nodig is om het resultaat te delen. Met andere woorden, als er een gesloten familie is waarin geen enkel element voorkomt in ten minste 1% van alle verzamelingen, is er meer informatie in de vereniging van twee verzamelingen dan in een van de verzamelingen zelf.
“Het idee om dingen element voor element te onthullen en te kijken naar de hoeveelheid informatie die je leert, is buitengewoon slim. Dat is het belangrijkste idee van het bewijs,” zei Ryan Alweiss van de Princeton-universiteit.
Op dit punt begon Gilmer het vermoeden van Frankl te naderen. Dat komt omdat het gemakkelijk is om aan te tonen dat in een gezin met gesloten vakbonden de vereniging van twee sets noodzakelijkerwijs minder informatie bevat dan de sets zelf - niet meer.
Om te zien waarom, denk eens aan die gesloten familie met de 1,024 verschillende sets die je kunt maken van de nummers 1 tot 10. Als je twee van die sets willekeurig kiest, krijg je gemiddeld sets met vijf elementen. (Van die 1,024 sets bevatten 252 vijf elementen, waardoor dat de meest voorkomende setgrootte is.) Je zult waarschijnlijk ook eindigen met een unie die ongeveer zeven elementen bevat. Maar er zijn slechts 120 verschillende manieren om sets te maken die zeven elementen bevatten.
Het punt is dat er meer onzekerheid is over de inhoud van twee willekeurig gekozen sets dan over hun vereniging. De unie scheef naar grotere sets met meer elementen, waarvoor minder mogelijkheden zijn. Als je de vereniging van twee sets in een gesloten familie neemt, weet je min of meer wat je gaat krijgen - zoals wanneer je een bevooroordeelde munt opgooit - wat betekent dat de unie minder informatie bevat dan de sets waaruit het is samengesteld.
Daarmee had Gilmer een bewijs. Hij wist dat als er geen enkel element in zelfs maar 1% van de sets voorkomt, de vakbond gedwongen is om meer informatie te bevatten. Maar de vakbond moet minder informatie bevatten. Daarom moet er minstens één element zijn dat voorkomt in minstens 1% van de sets.
De push naar 50
Toen Gilmer zijn bewijs op 16 november plaatste, voegde hij een notitie toe dat hij dacht dat het mogelijk was om zijn methode te gebruiken om nog dichter bij een bewijs van het volledige vermoeden te komen, waardoor de drempel mogelijk werd verhoogd tot 38%.
Vijf dagen later, drie anders groepen van de wiskundigen postte binnen enkele uren na elkaar papers die voortbouwden op het werk van Gilmer om precies dat te doen. Extra papieren gevolgd, maar de eerste uitbarsting lijkt de methoden van Gilmer zo ver te hebben gebracht als ze kunnen gaan; om tot 50% te komen, zijn waarschijnlijk extra nieuwe ideeën nodig.
Toch was het voor sommige auteurs van de follow-up papers relatief eenvoudig om 38% te bereiken, en ze vroegen zich af waarom Gilmer het niet gewoon zelf deed. De eenvoudigste verklaring bleek de juiste te zijn: na meer dan een half decennium zonder wiskunde wist Gilmer gewoon niet hoe hij een deel van het technische analytische werk moest doen dat nodig was om het voor elkaar te krijgen.
"Ik was een beetje roestig en om eerlijk te zijn zat ik vast", zei Gilmer. "Maar ik was benieuwd waar de gemeenschap het naartoe zou brengen."
Toch denkt Gilmer dat dezelfde omstandigheden die hem buiten de praktijk hielden, zijn bewijs waarschijnlijk in de eerste plaats mogelijk maakten.
"Het is de enige manier waarop ik kan uitleggen waarom ik op de graduate school een jaar lang over het probleem nadacht en geen vooruitgang boekte. Ik stopte zes jaar met wiskunde, keerde terug naar het probleem en maakte deze doorbraak", zei hij. "Ik weet niet hoe ik het moet uitleggen, behalve dat mijn denken door machine learning bevooroordeeld is."
correctie: 3 januari 2023
De oorspronkelijke kop verwees naar Gilmer als een 'Google-ingenieur'. In feite is hij een onderzoeker.
