Introduktion
I midten af oktober Justin Gilmer fløj fra Californien til New York for at deltage i en vens bryllup. Mens han var på østkysten, besøgte han sin tidligere rådgiver, Michael Saks, matematiker ved Rutgers University, hvor Gilmer havde modtaget sin doktorgrad syv år tidligere.
Saks og Gilmer indhentede frokosten, men de talte ikke om matematik. Faktisk havde Gilmer ikke tænkt seriøst over matematik, siden han afsluttede på Rutgers i 2015. Det var, da han havde besluttet, at han ikke ville have en karriere i den akademiske verden og i stedet begyndte at lære sig selv at programmere. Mens han og Saks spiste, fortalte Gilmer sin gamle mentor om sit job hos Google, hvor han arbejder med maskinlæring og kunstig intelligens.
Det var solskin den dag, Gilmer besøgte Rutgers. Mens han gik rundt, huskede han, hvordan han i 2013 havde brugt det meste af et år på at gå de samme stier på campus og tænkte på et problem kaldet den fagforeningslukkede formodning. Det havde været en fiksering, om end en frugtesløs en: På trods af alle sine anstrengelser var det kun lykkedes Gilmer at lære sig selv, hvorfor det tilsyneladende problem med talsæt var så svært at løse.
”Jeg tror, at mange tænker over problemet, indtil de bliver tilfredse med, at de forstår, hvorfor det er svært. Jeg brugte nok mere tid på det end de fleste mennesker,” sagde Gilmer.
Efter hans besøg i oktober skete der noget uventet: Han fik en ny idé. Gilmer begyndte at tænke på måder at anvende teknikker fra informationsteori til at løse den foreningslukkede formodning. Han forfulgte ideen i en måned og forventede hver gang, at den ville mislykkes. Men i stedet åbnede vejen til et bevis sig hele tiden. Endelig den 16. november han udsendte et første resultat af sin slags det får matematikere meget af vejen mod at bevise den fulde formodning.
Bladet satte gang i en byge af opfølgende arbejde. Matematikere ved University of Oxford, Massachusetts Institute of Technology og Institute for Advanced Study, blandt andre institutioner, byggede hurtigt videre på Gilmers nye metoder. Men før de gjorde det, stillede de deres eget spørgsmål: Hvem er lige denne fyr?
Halvt fuld
Den union-lukkede formodning handler om samlinger af tal kaldet sæt, såsom {1, 2} og {2, 3, 4}. Du kan udføre operationer på sæt, herunder tage deres forening, hvilket betyder at kombinere dem. For eksempel er foreningen af {1, 2} og {2, 3, 4} {1, 2, 3, 4}.
En samling, eller familie, af sæt betragtes som "forenings-lukket", hvis foreningen af to sæt i familien er lig med et eksisterende sæt i familien. Overvej for eksempel denne familie på fire sæt:
{1}, {1, 2}, {2, 3, 4}, {1, 2, 3, 4}.
Kombiner et hvilket som helst par, og du får et sæt, der allerede er i familien, hvilket gør familieforeningen lukket.
Matematikere snakkede om versioner af den fagforeningslukkede formodning så langt tilbage som i 1960'erne, men den modtog sin første formelle udtalelse i 1979, i et papir af Peter Frankl, en ungarsk matematiker, der emigrerede til Japan i 1980'erne, og som tæller gadeoptræden blandt sine sysler.
Frankl formodede, at hvis en familie af sæt er union-lukket, skal den have mindst ét element (eller tal), der optræder i mindst halvdelen af sættene. Det var en naturlig tærskel af to grunde.
For det første er der let tilgængelige eksempler på foreningslukkede familier, hvor alle elementer optræder i præcis 50 % af sætene. Ligesom alle de forskellige sæt, du kan lave fra f.eks. tallene 1 til 10. Der er 1,024 sådanne sæt, som danner en forenings-lukket familie, og hver af de 10 elementer optræder i 512 af dem. Og for det andet, på det tidspunkt, Frankl fremsatte formodningen, havde ingen nogensinde produceret et eksempel på en foreningslukket familie, hvor formodningen ikke holdt.
Så 50% virkede som den rigtige forudsigelse.
Det betød ikke, at det var nemt at bevise. I årene siden Frankls papir har der været få resultater. Før Gilmers arbejde var det kun lykkedes disse papirer at etablere tærskler, der varierede med antallet af sæt i familien (i modsætning til at være den samme tærskel på 50 % for sætfamilier af alle størrelser).
"Det føles som om det burde være nemt, og det ligner mange problemer, der er nemme, men det har modstået angreb," sagde Will Sawin fra Columbia University.
Manglen på fremskridt afspejlede både problemets vanskelige karakter og det faktum, at mange matematikere foretrak ikke at tænke over det; de var bekymrede for, at de ville miste årevis af deres karriere på jagt efter et forførende problem, som var umuligt at løse. Gilmer husker en dag i 2013, hvor han gik til Saks' kontor og tog den fagforeningslukkede formodning op. Hans rådgiver - som tidligere selv havde kæmpet med problemet - smed ham næsten ud af lokalet.
"Mike sagde," Justin, du får mig til at tænke over dette problem igen, og det vil jeg ikke gøre," sagde Gilmer.
En indsigt i usikkerhed
Efter sit besøg hos Rutgers rullede Gilmer problemet rundt i sit sind og forsøgte at forstå, hvorfor det var så svært. Han tilskyndede sig selv med en grundlæggende kendsgerning: Hvis du har en familie på 100 sæt, er der 4,950 forskellige måder at vælge to og tage deres fagforening på. Så spurgte han sig selv: Hvordan er det muligt, at 4,950 forskellige fagforeninger går tilbage til blot 100 sæt, hvis der ikke optræder noget element i disse fagforeninger med i det mindste en vis frekvens?
Selv på det tidspunkt var han på vej mod et bevis, selvom han ikke vidste det endnu. Teknikker fra informationsteori, som giver en streng måde at tænke på, hvad man kan forvente, når man trækker et par genstande tilfældigt, ville bringe ham derhen.
Informationsteori udviklet i første halvdel af det 20. århundrede, mest berømt med Claude Shannons papir fra 1948, "En matematisk teori om kommunikation." Papiret gav en præcis måde at beregne mængden af information, der er nødvendig for at sende en besked, baseret på mængden af usikkerhed omkring, hvad beskeden præcist ville sige. Dette link - mellem information og usikkerhed - var Shannons bemærkelsesværdige, grundlæggende indsigt.
For at tage et legetøjseksempel, forestil dig, at jeg vender en mønt fem gange og sender den resulterende sekvens til dig. Hvis det er en normal mønt, tager det fem informationsbits at sende. Men hvis det er en fyldt mønt - siger, 99% sandsynlighed for at lande på hoveder - kræver det meget mindre. For eksempel kunne vi aftale på forhånd, at jeg sender dig en 1 (en enkelt smule information), hvis den indlæste mønt lander hoveder alle fem gange, hvilket den med stor sandsynlighed vil gøre. Der er mere overraskelse i resultatet af en retfærdig møntvending, end der er med en forudindtaget, og derfor mere information.
Den samme tankegang gælder for informationen i talsæt. Hvis jeg har en familie af foreningslukkede sæt - siger de 1,024 sæt lavet af tallene 1 til 10 - kunne jeg vælge to sæt tilfældigt. Så kunne jeg kommunikere elementerne i hvert sæt til dig. Mængden af information, der skal til for at sende den besked, afspejler mængden af usikkerhed omkring, hvad disse elementer er: Der er f.eks. 50 % chance for, at det første element i det første sæt er et 1 (fordi 1 vises i halvdelen af sættene i familien), ligesom der er 50 % chance for, at det første resultat i en sekvens af fair møntslag er hoveder.
Informationsteori optræder ofte i kombinatorik, et matematikområde, der beskæftiger sig med at tælle objekter, hvilket er, hvad Gilmer havde studeret som kandidatstuderende. Men da han fløj hjem til Californien, bekymrede han sig for, at den måde, han mente at forbinde informationsteori med den lukkede fagforenings formodning, var en amatørs naive indsigt: Arbejdere matematikere havde sikkert stødt på denne skinnende genstand før og genkendt den som et fjols guld. .
"For at være ærlig er jeg lidt overrasket over, at ingen har tænkt på dette før," sagde Gilmer. "Men måske skulle jeg ikke blive overrasket, for jeg havde selv tænkt over det i et år, og jeg kendte informationsteori."
Mere sandsynligt end ikke
Gilmer arbejdede på problemet om natten, efter at have afsluttet sit arbejde hos Google, og i weekenden i hele anden halvdel af oktober og begyndelsen af november. Han blev opmuntret af ideer, som en gruppe matematikere havde udforsket år tidligere i en åbent samarbejde på bloggen til en fremtrædende matematiker ved navn Tim Gowers. Han arbejdede også med en lærebog ved sin side, så han kunne slå formler op, han havde glemt.
"Man skulle tro, at nogen, der kommer med et godt resultat, ikke skulle have konsulteret kapitel 2 af Elementer af informationsteori, men det gjorde jeg,” sagde Gilmer.
Gilmers strategi var at forestille sig en forenings-lukket familie, hvor intet element optrådte i selv 1% af alle sæt - et modeksempel, der, hvis det virkelig eksisterede, ville forfalske Frankls formodning.
Lad os sige, at du vælger to sæt, A og B, fra denne familie tilfældigt og overvejer de elementer, der kunne være i disse sæt, et ad gangen. Spørg nu: Hvad er oddsene for, at sæt A indeholder tallet 1? Og sæt B? Da hvert element har lidt mindre end 1 % chance for at dukke op i et givet sæt, ville du ikke forvente, at hverken A eller B indeholder 1. Hvilket betyder, at der er lidt overraskelse - og lidt information opnået - hvis du opdager det, hverken i virkeligheden gør.
Tænk derefter på chancen for, at foreningen af A og B indeholder 1. Det er stadig usandsynligt, men det er mere sandsynligt end oddsene, at det optræder i et af de individuelle sæt. Det er summen af sandsynligheden for, at den vises i A og sandsynligheden for, at den vises i B minus sandsynligheden for, at den vises i begge. Så måske lige under 2%.
Dette er stadig lavt, men det er tættere på et 50-50-forslag. Det betyder, at det kræver mere information at dele resultatet. Med andre ord, hvis der er en foreningslukket familie, hvor intet element optræder i mindst 1 % af alle sæt, er der mere information i foreningen af to sæt end i selve sættet.
"Idéen med at afsløre ting element for element og se på mængden af information, du lærer, er ekstremt smart. Det er hovedtanken med beviset,” sagde Ryan Alweiss fra Princeton University.
På dette tidspunkt begyndte Gilmer at nærme sig Frankls formodning. Det er fordi det er nemt at påvise, at i en foreningslukket familie indeholder foreningen af to sæt nødvendigvis mindre information end selve sættene - ikke mere.
For at se hvorfor, tænk på den foreningslukkede familie, der indeholder de 1,024 forskellige sæt, du kan lave fra tallene 1 til 10. Hvis du vælger to af disse sæt tilfældigt, ender du i gennemsnit med sæt, der indeholder fem elementer. (Af disse 1,024 sæt indeholder 252 fem elementer, hvilket gør det til den mest almindelige sætstørrelse.) Du vil sandsynligvis også ende med en forening, der indeholder omkring syv elementer. Men der er kun 120 forskellige måder at lave sæt med syv elementer på.
Pointen er, at der er mere usikkerhed om indholdet af to tilfældigt udvalgte sæt, end der er om deres forening. Fagforeningen skæver til større sæt med flere elementer, som der er færre muligheder for. Når du tager foreningen af to sæt i en foreningslukket familie, ved du på en måde, hvad du vil få - som når du vender en forudindtaget mønt - hvilket betyder, at foreningen indeholder mindre information end de sæt, den er sammensat af.
Med det havde Gilmer et bevis. Han vidste, at hvis intet element forekommer i selv 1% af sætene, er fagforeningen tvunget til at indeholde flere oplysninger. Men fagforeningen skal indeholde færre oplysninger. Derfor skal der være mindst ét element, der optræder i mindst 1 % af sættene.
Skub til 50
Da Gilmer postede sit bevis den 16. november, inkluderede han en note om, at han mente, at det var muligt at bruge hans metode til at komme endnu tættere på et bevis for den fulde formodning, hvilket potentielt hævede tærsklen til 38 %.
Fem dage senere, tre forskellige grupper af matematikere postede papirer inden for få timer efter hinanden, der byggede på Gilmers arbejde for at gøre netop det. Yderligere papirer efterfulgt, men det indledende udbrud synes at have ført Gilmers metoder så langt, som de vil gå; at nå 50 % vil sandsynligvis kræve yderligere nye ideer.
Alligevel var det for nogle af forfatterne af opfølgende papirer at komme til 38% relativt ligetil, og de undrede sig over, hvorfor Gilmer ikke bare gjorde det selv. Den enkleste forklaring viste sig at være den rigtige: Efter mere end et halvt årti uden matematik vidste Gilmer bare ikke, hvordan han skulle udføre noget af det tekniske analytiske arbejde, der krævede for at klare det.
"Jeg var lidt rusten, og for at være ærlig sad jeg fast," sagde Gilmer. "Men jeg var ivrig efter at se, hvor samfundet ville tage det."
Alligevel mener Gilmer, at de samme omstændigheder, der lod ham ude af praksis, sandsynligvis gjorde hans bevis muligt i første omgang.
"Det er den eneste måde, jeg kan forklare, hvorfor jeg tænkte på problemet i et år på kandidatskolen og ikke gjorde fremskridt, jeg forlod matematik i seks år, og vendte derefter tilbage til problemet og fik dette gennembrud," sagde han. "Jeg ved ikke, hvordan jeg skal forklare det, andet end at være i maskinlæring påvirkede min tankegang."
Rettelse: Januar 3, 2023
Den originale overskrift omtalte Gilmer som en "Google-ingeniør". Faktisk er han forsker.
