Introduksjon
I midten av oktober, Justin Gilmer fløy fra California til New York for å delta i en venns bryllup. Mens han var på østkysten besøkte han sin tidligere rådgiver, Michael Saks, en matematiker ved Rutgers University, hvor Gilmer hadde tatt doktorgraden syv år tidligere.
Saks og Gilmer tok en lunsj, men de snakket ikke om matematikk. Faktisk hadde Gilmer ikke tenkt seriøst på matematikk siden han avsluttet ved Rutgers i 2015. Det var da han bestemte seg for at han ikke ville ha en karriere i akademia og begynte i stedet å lære seg selv å programmere. Mens han og Saks spiste, fortalte Gilmer sin gamle mentor om jobben sin hos Google, hvor han jobber med maskinlæring og kunstig intelligens.
Det var sol den dagen Gilmer besøkte Rutgers. Mens han gikk rundt, husket han hvordan han i 2013 hadde brukt mesteparten av et år på å gå de samme campusstiene, og tenkte på et problem kalt den fagforeningslukkede formodningen. Det hadde vært en fiksering, om enn fruktløs: Til tross for all sin innsats hadde Gilmer bare lykkes i å lære seg selv hvorfor det enkle tilsynelatende problemet med tallsett var så vanskelig å løse.
"Jeg tror mange tenker på problemet til de blir fornøyde med at de forstår hvorfor det er vanskelig. Jeg brukte sannsynligvis mer tid på det enn de fleste, sa Gilmer.
Etter besøket i oktober skjedde noe uventet: Han fikk en ny idé. Gilmer begynte å tenke på måter å anvende teknikker fra informasjonsteori for å løse den fagforeningslukkede formodningen. Han fulgte ideen i en måned, og ventet på hver tur at den skulle mislykkes. Men i stedet åpnet veien til et bevis seg stadig. Til slutt, den 16. november han la ut et første resultat i sitt slag som får matematikere mye av veien mot å bevise hele formodningen.
Avisen satte i gang en mengde oppfølgingsarbeid. Matematikere ved University of Oxford, Massachusetts Institute of Technology og Institute for Advanced Study, blant andre institusjoner, bygde raskt på Gilmers nye metoder. Men før de gjorde det, stilte de et eget spørsmål: Hvem er denne fyren?
Halvfull
Den fagforeningslukkede formodningen handler om samlinger av tall kalt sett, som {1, 2} og {2, 3, 4}. Du kan utføre operasjoner på sett, inkludert å ta deres union, som betyr å kombinere dem. For eksempel er foreningen av {1, 2} og {2, 3, 4} {1, 2, 3, 4}.
En samling, eller familie, av sett regnes som "foreningslukket" hvis foreningen av to sett i familien tilsvarer et eksisterende sett i familien. Tenk for eksempel på denne familien på fire sett:
{1}, {1, 2}, {2, 3, 4}, {1, 2, 3, 4}.
Kombiner et par og du får et sett som allerede er i familien, noe som gjør familieforeningen stengt.
Matematikere pratet om versjoner av den forbundslukkede formodningen så langt tilbake som på 1960-tallet, men den mottok sin første formelle uttalelse i 1979, i en artikkel av Peter Frankl, en ungarsk matematiker som emigrerte til Japan på 1980-tallet og som regner gateopptreden blant sine sysler.
Frankl antok at hvis en familie av sett er union-lukket, må den ha minst ett element (eller nummer) som vises i minst halvparten av settene. Det var en naturlig terskel av to grunner.
For det første er det lett tilgjengelige eksempler på foreningslukkede familier der alle elementer forekommer i nøyaktig 50 % av settene. Som alle de forskjellige settene du kan lage fra tallene 1 til 10, for eksempel. Det er 1,024 slike sett, som danner en foreningslukket familie, og hvert av de 10 elementene vises i 512 av dem. Og for det andre, på det tidspunktet Frankl kom med antagelsen hadde ingen noen gang produsert et eksempel på en foreningslukket familie der formodningen ikke holdt.
Så 50 % virket som den riktige spådommen.
Det betydde ikke at det var lett å bevise. I årene etter Frankls artikkel har det vært få resultater. Før Gilmers arbeid klarte disse papirene bare å etablere terskler som varierte med antall sett i familien (i motsetning til å være den samme 50 %-terskelen for settfamilier av alle størrelser).
"Det føles som om det burde være enkelt, og det ligner på mange problemer som er enkle, men det har motstått angrep," sa Will Sawin ved Columbia University.
Mangelen på fremgang reflekterte både problemets vanskelige natur og det faktum at mange matematikere foretrakk å ikke tenke på det; de var bekymret for at de ville miste år av karrieren sin på jakt etter et forlokkende problem som var umulig å løse. Gilmer husker en dag i 2013 da han dro til Saks' kontor og tok opp den fagforeningslukkede formodningen. Rådgiveren hans - som tidligere hadde kjempet med problemet selv - nesten kastet ham ut av rommet.
"Mike sa," Justin, du kommer til å få meg til å tenke på dette problemet igjen, og jeg vil ikke gjøre det," sa Gilmer.
En innsikt i usikkerhet
Etter besøket til Rutgers, rullet Gilmer problemet rundt i tankene, og prøvde å forstå hvorfor det var så vanskelig. Han spurte seg selv med et grunnleggende faktum: Hvis du har en familie på 100 sett, er det 4,950 forskjellige måter å velge to og ta deres forening. Så spurte han seg selv: Hvordan er det mulig at 4,950 forskjellige fagforeninger kartlegges tilbake til bare 100 sett hvis det ikke vises noe element i disse fagforeningene med i det minste en viss frekvens?
Selv på det tidspunktet var han på vei til et bevis, selv om han ikke visste det ennå. Teknikker fra informasjonsteori, som gir en streng måte å tenke på hva du kan forvente når du trekker et par gjenstander tilfeldig, ville tatt ham dit.
Informasjonsteori utviklet i første halvdel av det 20. århundre, mest kjent med Claude Shannons artikkel fra 1948, "En matematisk teori for kommunikasjon." Oppgaven ga en presis måte å beregne mengden informasjon som trengs for å sende en melding, basert på mengden usikkerhet rundt hva meldingen nøyaktig ville si. Denne lenken - mellom informasjon og usikkerhet – var Shannons bemerkelsesverdige, grunnleggende innsikt.
For å ta et lekeeksempel, forestill deg at jeg slår en mynt fem ganger og sender den resulterende sekvensen til deg. Hvis det er en vanlig mynt, tar det fem informasjonsbiter å overføre. Men hvis det er en lastet mynt - si, 99% sannsynlighet for å lande på hodet - krever det mye mindre. For eksempel kan vi avtale på forhånd at jeg sender deg en 1 (en enkelt bit informasjon) hvis den innlastede mynten lander på hodet alle fem gangene, noe den er svært sannsynlig å gjøre. Det er mer overraskelse i utfallet av en rettferdig myntvending enn det er med en partisk en, og derfor mer informasjon.
Den samme tankegangen gjelder for informasjonen i tallsett. Hvis jeg har en familie med foreningslukkede sett - si de 1,024 settene laget av tallene 1 til 10 - kunne jeg velge to sett tilfeldig. Da kunne jeg formidle elementene i hvert sett til deg. Mengden informasjon som kreves for å sende den meldingen gjenspeiler mengden av usikkerhet rundt hva disse elementene er: Det er for eksempel 50 % sjanse for at det første elementet i det første settet er en 1 (fordi 1 vises i halvparten av settene i familien), akkurat som det er 50 % sjanse for at det første resultatet i en sekvens med rettferdige myntsving er hoder.
Informasjonsteori dukker ofte opp i kombinatorikk, et matematikkområde opptatt av å telle objekter, som er det Gilmer hadde studert som hovedfagsstudent. Men da han fløy hjem til California, bekymret han seg for at måten han tenkte å koble informasjonsteori til den lukkede fagforenings-formodningen var den naive innsikten til en amatør: Arbeidende matematikere hadde sikkert kommet over denne skinnende gjenstanden før og anerkjent den som idiots gull .
"For å være ærlig er jeg litt overrasket over at ingen har tenkt på dette før," sa Gilmer. "Men jeg burde kanskje ikke bli overrasket, for jeg hadde selv tenkt på det i et år, og jeg kunne informasjonsteori."
Mer sannsynlig enn ikke
Gilmer jobbet med problemet om natten, etter å ha avsluttet arbeidet hos Google, og i helgene gjennom andre halvdel av oktober og begynnelsen av november. Han ble oppmuntret av ideer som en gruppe matematikere hadde utforsket år tidligere i en åpent samarbeid på bloggen til en fremtredende matematiker ved navn Tim Gowers. Han jobbet også med en lærebok ved sin side slik at han kunne slå opp formler han hadde glemt.
"Du skulle tro at noen som kommer opp med et flott resultat, ikke burde måtte konsultere kapittel 2 av Elementer i informasjonsteori, men jeg gjorde det, sa Gilmer.
Gilmers strategi var å forestille seg en foreningslukket familie der ingen elementer dukket opp i selv 1% av alle settene - et moteksempel som, hvis det virkelig eksisterte, ville forfalske Frankls formodning.
La oss si at du velger to sett, A og B, fra denne familien tilfeldig og vurderer elementene som kan være i disse settene, ett om gangen. Spør nå: Hva er oddsen for at sett A inneholder tallet 1? Og sett B? Siden hvert element har litt mindre enn 1 % sjanse for å dukke opp i et gitt sett, ville du ikke forvente at verken A eller B inneholder 1. Det betyr at det er liten overraskelse – og lite informasjon oppnådd – hvis du lærer at verken faktisk gjør.
Tenk deretter på sjansen for at foreningen av A og B inneholder 1. Det er fortsatt usannsynlig, men det er mer sannsynlig enn oddsen at det vises i et av de individuelle settene. Det er summen av sannsynligheten for at den vises i A og sannsynligheten for at den vises i B minus sannsynligheten for at den vises i begge. Så kanskje i underkant av 2%.
Dette er fortsatt lavt, men det er nærmere et 50-50-forslag. Det betyr at det kreves mer informasjon for å dele resultatet. Med andre ord, hvis det er en foreningslukket familie der det ikke vises noe element i minst 1 % av alle settene, er det mer informasjon i foreningen av to sett enn i noen av selve settene.
"Ideen om å avsløre ting element for element og se på mengden informasjon du lærer er ekstremt smart. Det er hovedideen med beviset,» sa Ryan Alweiss fra Princeton University.
På dette tidspunktet begynte Gilmer å nærme seg Frankls formodning. Det er fordi det er lett å demonstrere at i en foreningslukket familie, inneholder foreningen av to sett nødvendigvis mindre informasjon enn selve settene – ikke mer.
For å se hvorfor, tenk på den foreningslukkede familien som inneholder de 1,024 forskjellige settene du kan lage fra tallene 1 til 10. Hvis du velger to av disse settene tilfeldig, vil du i gjennomsnitt ende opp med sett som inneholder fem elementer. (Av disse 1,024 settene inneholder 252 fem elementer, noe som gjør det til den vanligste settstørrelsen.) Du vil også sannsynligvis ende opp med en forening som inneholder omtrent syv elementer. Men det er bare 120 forskjellige måter å lage sett som inneholder syv elementer.
Poenget er at det er mer usikkerhet om innholdet i to tilfeldig utvalgte sett enn det er om deres forening. Forbundet skjever til større sett med flere elementer, som det er færre muligheter for. Når du tar foreningen av to sett i en foreningslukket familie, vet du på en måte hva du kommer til å få - som når du snur en forutinntatt mynt - som betyr at foreningen inneholder mindre informasjon enn settene den består av.
Med det hadde Gilmer et bevis. Han visste at hvis det ikke vises noe element i selv 1% av settene, er fagforeningen tvunget til å inneholde mer informasjon. Men forbundet må inneholde mindre informasjon. Derfor må det være minst ett element som vises i minst 1 % av settene.
Push til 50
Da Gilmer la ut beviset sitt 16. november, inkluderte han et notat om at han trodde det var mulig å bruke metoden hans for å komme enda nærmere et bevis på hele formodningen, noe som potensielt kunne heve terskelen til 38 %.
Fem dager senere, tre forskjellig grupper av matematikere la ut artikler innen timer etter hverandre som bygde på Gilmers arbeid for å gjøre nettopp det. Ytterligere papirer fulgt, men det første utbruddet ser ut til å ha tatt Gilmers metoder så langt de vil gå; å komme til 50 % vil sannsynligvis kreve flere nye ideer.
Likevel, for noen av forfatterne av oppfølgingspapirene var det relativt enkelt å komme til 38 %, og de lurte på hvorfor Gilmer ikke bare gjorde det selv. Den enkleste forklaringen viste seg å være den riktige: Etter mer enn et halvt tiår uten matematikk, visste ikke Gilmer hvordan han skulle gjøre noe av det tekniske analytiske arbeidet som kreves for å klare det.
"Jeg var litt rusten, og for å være ærlig satt jeg fast," sa Gilmer. "Men jeg var ivrig etter å se hvor samfunnet ville ta det."
Likevel tror Gilmer at de samme omstendighetene som slapp ham ut av praksis sannsynligvis gjorde beviset hans mulig i utgangspunktet.
"Det er den eneste måten jeg kan forklare hvorfor jeg tenkte på problemet i et år på forskerskolen og ikke gjorde noen fremgang, jeg forlot matematikk i seks år, så vendte jeg tilbake til problemet og fikk dette gjennombruddet," sa han. "Jeg vet ikke hvordan jeg skal forklare det annet enn at det å være i maskinlæring påvirket tankegangen min."
Korreksjon: Januar 3, 2023
Den opprinnelige overskriften refererte til Gilmer som en "Google-ingeniør." Faktisk er han en forsker.
