Beskrivning
I mitten av oktober, Justin Gilmer flög från Kalifornien till New York för att delta på en väns bröllop. Medan han var på östkusten besökte han sin tidigare rådgivare, Michael Saks, en matematiker vid Rutgers University, där Gilmer hade doktorerat sju år tidigare.
Saks och Gilmer kom ikapp över lunch, men de pratade inte om matematik. Faktum är att Gilmer inte hade tänkt seriöst på matematik sedan han slutade på Rutgers 2015. Det var då han hade bestämt sig för att han inte ville ha en karriär inom den akademiska världen och istället började lära sig programmera. När han och Saks åt berättade Gilmer för sin gamla mentor om sitt jobb på Google, där han arbetar med maskininlärning och artificiell intelligens.
Det var soligt den dagen Gilmer besökte Rutgers. När han gick runt mindes han hur han under 2013 hade tillbringat större delen av ett år på att gå samma campusvägar, och tänkt på ett problem som kallas den fackligt slutna gissningen. Det hade varit en fixering, om än fruktlös: Trots all sin ansträngning hade Gilmer bara lyckats lära sig själv varför det enkelt till synes problem med taluppsättningar var så svårt att lösa.
”Jag tror att många tänker på problemet tills de blir nöjda med att de förstår varför det är svårt. Jag tillbringade förmodligen mer tid på det än de flesta, säger Gilmer.
Efter hans besök i oktober hände något oväntat: Han fick en ny idé. Gilmer började fundera på sätt att tillämpa tekniker från informationsteori för att lösa den fackligt slutna gissningen. Han fortsatte med idén i en månad och förväntade sig vid varje tur att den skulle misslyckas. Men istället öppnades vägen till ett bevis hela tiden. Slutligen, den 16 november han publicerade ett första resultat i sitt slag som får matematiker mycket av vägen mot att bevisa den fullständiga gissningen.
Tidningen satte igång en uppsjö av uppföljningsarbete. Matematiker vid University of Oxford, Massachusetts Institute of Technology och Institute for Advanced Study, bland andra institutioner, byggde snabbt på Gilmers nya metoder. Men innan de gjorde det ställde de en egen fråga: Vem är den här killen?
Halvfull
Den fackligt slutna gissningen handlar om samlingar av tal som kallas mängder, som {1, 2} och {2, 3, 4}. Du kan utföra operationer på set, inklusive att ta deras union, vilket innebär att kombinera dem. Till exempel är föreningen av {1, 2} och {2, 3, 4} {1, 2, 3, 4}.
En samling, eller familj, av uppsättningar anses vara "fackligt slutna" om sammanslutningen av två uppsättningar i familjen är lika med alla befintliga uppsättningar i familjen. Tänk till exempel på den här familjen med fyra uppsättningar:
{1}, {1, 2}, {2, 3, 4}, {1, 2, 3, 4}.
Kombinera vilket par som helst och du får ett set som redan finns i familjen, vilket gör familjeförbundet stängt.
Matematiker pratade om versioner av den fackligt slutna gissningen så långt tillbaka som på 1960-talet, men den fick sitt första formella uttalande 1979, i en tidning av Peter Frankl, en ungersk matematiker som emigrerade till Japan på 1980-talet och som räknar gatuuppträdande till sina sysselsättningar.
Frankl antog att om en familj av uppsättningar är fackligt sluten, måste den ha minst ett element (eller nummer) som förekommer i minst hälften av uppsättningarna. Det var en naturlig tröskel av två anledningar.
För det första finns det lättillgängliga exempel på fackligt slutna familjer där alla element förekommer i exakt 50 % av uppsättningarna. Som alla olika uppsättningar du kan göra från siffrorna 1 till 10, till exempel. Det finns 1,024 10 sådana uppsättningar, som bildar en fackligt sluten familj, och vart och ett av de 512 elementen förekommer i XNUMX av dem. Och för det andra, när Frankl gjorde gissningen hade ingen någonsin tagit fram ett exempel på en fackligt sluten familj där gissningarna inte höll.
Så 50% verkade vara den rätta förutsägelsen.
Det betydde inte att det var lätt att bevisa. Under åren sedan Frankls tidning har det varit få resultat. Före Gilmers arbete lyckades dessa papper bara fastställa trösklar som varierade med antalet uppsättningar i familjen (i motsats till att vara samma tröskel på 50 % för uppsättningsfamiljer av alla storlekar).
"Det känns som att det borde vara lätt, och det liknar många problem som är lätta, men det har motstått attacker," sa Will Sawin vid Columbia University.
Bristen på framsteg speglade både problemets knepiga natur och det faktum att många matematiker föredrog att inte tänka på det; de oroade sig för att de skulle förlora år av sina karriärer på att jaga ett lockande problem som var omöjligt att lösa. Gilmer minns en dag 2013 när han gick till Saks kontor och tog upp den fackligt slutna gissningen. Hans rådgivare – som tidigare hade brottats med problemet själv – nästan kastade ut honom ur rummet.
"Mike sa," Justin, du kommer att få mig att tänka på det här problemet igen och jag vill inte göra det," sa Gilmer.
En insikt om osäkerhet
Efter sitt besök hos Rutgers rullade Gilmer på problemet i tankarna och försökte förstå varför det var så svårt. Han uppmanade sig själv med ett grundläggande faktum: Om du har en familj på 100 set finns det 4,950 4,950 olika sätt att välja två och ta deras förening. Sedan frågade han sig själv: Hur är det möjligt att 100 XNUMX olika förbund mappar tillbaka till bara XNUMX uppsättningar om inget element förekommer i dessa förbund med åtminstone en viss frekvens?
Även vid den tidpunkten var han på väg mot ett bevis, även om han inte visste det ännu. Tekniker från informationsteorin, som ger ett rigoröst sätt att tänka på vad man kan förvänta sig när man drar ett par föremål på måfå, skulle ta honom dit.
Informationsteori utvecklades under första hälften av 20-talet, mest känd med Claude Shannons artikel från 1948, "En matematisk kommunikationsteori.” Tidningen gav ett exakt sätt att beräkna mängden information som behövs för att skicka ett meddelande, baserat på mängden osäkerhet kring exakt vad meddelandet skulle säga. Den här länken - mellan information och osäkerhet — var Shannons anmärkningsvärda, grundläggande insikt.
För att ta ett leksaksexempel, föreställ dig att jag slår ett mynt fem gånger och skickar den resulterande sekvensen till dig. Om det är ett vanligt mynt tar det fem informationsbitar att överföra. Men om det är ett laddat mynt - säg, 99% sannolikt att landa på huvuden - krävs det mycket mindre. Till exempel kan vi komma överens i förväg om att jag skickar dig en 1 (en enstaka bit information) om det laddade myntet landar huvuden alla fem gångerna, vilket det är mycket troligt att göra. Det finns mer överraskning i resultatet av en rättvis myntvändning än det är med en partisk, och därför mer information.
Samma tankesätt gäller för informationen i siffror. Om jag har en familj av fackligt slutna uppsättningar - säg de 1,024 1 uppsättningarna gjorda av siffrorna 10 till 50 - skulle jag kunna välja två uppsättningar slumpmässigt. Sedan kunde jag kommunicera elementen i varje uppsättning till dig. Mängden information som krävs för att skicka meddelandet återspeglar mängden osäkerhet kring vad dessa element är: Det finns till exempel 1 % chans att det första elementet i den första uppsättningen är en 1 (eftersom 50 visas i hälften av uppsättningarna i familjen), precis som det finns XNUMX % chans att det första resultatet i en sekvens av rättvisa myntvändningar är huvuden.
Informationsteori förekommer ofta i kombinatorik, ett område inom matematik som handlar om att räkna objekt, vilket är vad Gilmer hade studerat som doktorand. Men när han flög tillbaka hem till Kalifornien, oroade han sig för att sättet han tänkte koppla informationsteorin till den slutna fackliga gissningen var en amatörs naiva insikt: Arbetande matematiker hade säkert stött på detta glänsande föremål förut och känt igen det som dåraktigt guld. .
"För att vara ärlig, jag är lite förvånad över att ingen tänkt på det här tidigare," sa Gilmer. "Men jag borde kanske inte bli förvånad, för jag hade själv tänkt på det i ett år och jag kunde informationsteori."
Mer troligt än inte
Gilmer arbetade med problemet på natten, efter att ha avslutat sitt arbete på Google, och på helgerna under andra hälften av oktober och början av november. Han uppmuntrades av idéer som en grupp matematiker hade utforskat år tidigare i en öppet samarbete på bloggen till en framstående matematiker vid namn Tim Gowers. Han arbetade också med en lärobok vid sin sida så att han kunde slå upp formler som han hade glömt.
"Man skulle kunna tro att någon som kommer med ett bra resultat inte borde behöva konsultera kapitel 2 av Delar av informationsteori, men det gjorde jag, sa Gilmer.
Gilmers strategi var att föreställa sig en fackligt sluten familj där inget element förekom i ens 1% av alla uppsättningar – ett motexempel som, om det verkligen existerade, skulle förfalska Frankls gissningar.
Låt oss säga att du väljer två uppsättningar, A och B, från den här familjen på måfå och överväger de element som kan finnas i dessa uppsättningar, en i taget. Fråga nu: Vad är oddsen för att set A innehåller siffran 1? Och set B? Eftersom varje element har lite mindre än 1 % chans att dyka upp i en given uppsättning, skulle du inte förvänta dig att vare sig A eller B skulle innehålla 1. Vilket betyder att det finns liten överraskning – och lite information att få – om du lär dig att varken i själva verket gör.
Tänk sedan på chansen att föreningen av A och B innehåller 1. Det är fortfarande osannolikt, men det är mer troligt än oddsen att det dyker upp i någon av de individuella seten. Det är summan av sannolikheten att det visas i A och sannolikheten att det visas i B minus sannolikheten att det visas i båda. Så kanske strax under 2%.
Detta är fortfarande lågt, men det är närmare ett 50-50-förslag. Det betyder att det krävs mer information för att dela resultatet. Med andra ord, om det finns en fackligt sluten familj där inget element förekommer i minst 1 % av alla uppsättningar, finns det mer information i sammanslutningen av två uppsättningar än i någon av uppsättningarna själva.
"Idén att avslöja saker element för element och titta på mängden information du lär dig är extremt smart. Det är huvudtanken med beviset”, sa Ryan Alweiss från Princeton University.
Vid det här laget började Gilmer närma sig Frankls gissningar. Det beror på att det är lätt att visa att i en fackligt sluten familj innehåller föreningen av två uppsättningar nödvändigtvis mindre information än själva uppsättningarna – inte mer.
För att se varför, tänk på den fackligt slutna familjen som innehåller de 1,024 1 olika uppsättningarna du kan göra från siffrorna 10 till 1,024. Om du väljer två av dessa uppsättningar slumpmässigt, kommer du i genomsnitt att sluta med uppsättningar som innehåller fem element. (Av dessa 252 120 uppsättningar innehåller XNUMX fem element, vilket gör det till den vanligaste uppsättningsstorleken.) Du kommer sannolikt också att sluta med en förening som innehåller cirka sju element. Men det finns bara XNUMX olika sätt att göra set som innehåller sju element.
Poängen är att det finns mer osäkerhet om innehållet i två slumpmässigt utvalda uppsättningar än om deras förening. Förbundet snedställer sig till större uppsättningar med fler element, som det finns färre möjligheter för. När du tar föreningen av två uppsättningar i en fackligt sluten familj, vet du ungefär vad du kommer att få - som när du vänder ett partiskt mynt - vilket innebär att föreningen innehåller mindre information än de uppsättningar den består av.
Med det hade Gilmer ett bevis. Han visste att om inget element förekommer i ens 1% av uppsättningarna, tvingas facket innehålla mer information. Men facket måste innehålla mindre information. Därför måste det finnas minst ett element som förekommer i minst 1 % av uppsättningarna.
Push till 50
När Gilmer publicerade sitt bevis den 16 november inkluderade han en anteckning om att han trodde att det var möjligt att använda sin metod för att komma ännu närmare ett bevis på hela gissningen, vilket potentiellt kunde höja tröskeln till 38 %.
Fem dagar senare, tre olika grupper av matematiker postade papper inom några timmar efter varandra som byggde på Gilmers arbete för att göra just det. Annat papper följt, men den inledande sprängningen verkar ha tagit Gilmers metoder så långt de kommer att gå; att nå 50 % kommer sannolikt att kräva ytterligare nya idéer.
Ändå var det relativt enkelt för några av författarna till uppföljningsartiklarna att nå 38 %, och de undrade varför Gilmer inte bara gjorde det själv. Den enklaste förklaringen visade sig vara den korrekta: Efter mer än ett halvt decennium utan matematik visste Gilmer helt enkelt inte hur han skulle göra en del av det tekniska analysarbete som krävdes för att klara det.
"Jag var lite rostig, och för att vara ärlig, jag var fast," sa Gilmer. "Men jag var angelägen om att se vart samhället skulle ta det."
Ändå tror Gilmer att samma omständigheter som lämnade honom utanför praktiken förmodligen gjorde hans bevis möjligt i första hand.
"Det är det enda sättet jag kan förklara varför jag tänkte på problemet i ett år i forskarskolan och inte gjorde några framsteg, jag lämnade matematiken i sex år, sedan återvände till problemet och fick det här genombrottet", sa han. "Jag vet inte hur jag ska förklara det, annat än att jag var i maskininlärning påverkade mitt tänkande."
Rättelse: Januari 3, 2023
Den ursprungliga rubriken hänvisade till Gilmer som en "Google-ingenjör". I själva verket är han en forskare.
