'A-Team' of Math bevisar en kritisk länk mellan addition och set | Quanta Magazine

I en slumpmässigt vald uppsättning siffror kan addition bli vild.

Lägg ihop varje par från en sådan uppsättning, så kommer du att få en ny lista som sannolikt kommer att ha mycket fler siffror än vad du började med. Börja med 10 slumpmässiga tal, och den här nya listan (kallad summamängd) kommer att ha cirka 50 element. Börja med 100 och summan kommer förmodligen att ha runt 5,000 1,000; 500,000 XNUMX slumpmässiga initiala nummer kommer att göra en summa XNUMX XNUMX nummer lång.

Men om din initiala uppsättning har struktur kan summamängden sluta med färre siffror än så här. Tänk på en annan 10-talsuppsättning: alla de jämna talen från 2 till 20. Eftersom olika par kommer att läggas till samma nummer — 10 + 12 är samma som 8 + 14 och 6 + 16 — har summamängden bara 19 tal, inte 50. Denna skillnad blir mer och mer djupgående när uppsättningarna blir större. En strukturerad lista med 1,000 2,000 nummer kan ha en summa med bara XNUMX XNUMX nummer i den.

På 1960-talet hette en matematiker Gregory Freiman började undersöka uppsättningar med små summängder i ett försök att undersöka sambandet mellan addition och mängdstruktur - en avgörande koppling som definierar det matematiska området för additiv kombinatorik. Freiman gjorde imponerande framsteg och bevisade att en uppsättning med en liten summa måste innehållas av en större uppsättning vars element är fördelade i ett mycket regelbundet mönster. Men sedan stagnerade fältet. "Freimans ursprungliga bevis var utomordentligt svårt att förstå, till den grad att ingen verkligen var helt säker på att det var korrekt. Så det hade inte riktigt den inverkan som det kan ha haft”, sa Timothy Gowers, en matematiker vid Collège de France och University of Cambridge och en Fields-medaljör. "Men då Imre Ruzsa kom in på platsen."

I en serie av två papper på 1990-talet bevisade Ruzsa Freimans teorem på nytt med ett elegant nytt argument. Några år senare, Katalin Marton, en inflytelserik ungersk matematiker som dog 2019, justerade frågan om vad en liten summa innebär om strukturen för den ursprungliga uppsättningen. Hon ersatte de typer av element som förekom i uppsättningen och den typ av struktur som matematiker borde leta efter, och tänkte som skulle göra det möjligt för matematiker att extrahera ännu mer information. Martons gissningar har kopplingar till bevissystem, kodningsteori och kryptografi, och intar en upphöjd plats inom additiv kombinatorik.

Hennes gissningar "känns verkligen som en av de mest grundläggande sakerna som vi inte förstod," sa Ben Green, matematiker vid University of Oxford. Det "bara underbyggde massor av saker som jag bryr mig om."

Green gick samman med Gowers, Freddie Manners vid University of California, San Diego, och Terence tao, en Fields-medaljör vid University of California, Los Angeles för att bilda vad den israeliska matematikern och bloggaren Gil Kalai kallas en "Ett lag” av matematiker. De bevisade en version av gissningen i en tidning delades den 9 november.

Nets Katz, en matematiker vid Rice University som inte var involverad i arbetet, beskriver beviset som "vackert okomplicerat" - och "mer eller mindre helt ur det blå."

Tao startade sedan ett försök att formalisera beviset Lean, ett programmeringsspråk som hjälper matematiker att verifiera satser. På bara några veckor lyckades den insatsen. Tidigt tisdag morgon den 5 december, Tao meddelade att Lean hade bevisat gissningen utan några "sorrys" - standardsatsen som visas när datorn inte kan verifiera ett visst steg. Detta är den högst uppmärksammade användningen av sådana verifieringsverktyg sedan 2021, och markerar en böjningspunkt i hur matematiker skriver bevis i termer som en dator kan förstå. Om dessa verktyg blir enkla nog för matematiker att använda, kanske de kan ersätta den ofta utdragna och betungande peer review-processen, sa Gowers.

Beståndsdelarna i beviset hade puttrat i årtionden. Gowers tänkte på sina första steg i början av 2000-talet. Men det tog 20 år att bevisa vad Kalai kallade "en helig gral" av fältet.

In-gruppen

För att förstå Martons gissningar hjälper det att vara bekant med begreppet en grupp, ett matematiskt objekt som består av en mängd och en operation. Tänk på heltalen - en oändlig uppsättning tal - och additionsfunktionen. Varje gång du adderar två heltal får du ett annat heltal. Addition följer också några andra regler för gruppoperationer, som associativitet, som låter dig ändra ordningen på operationer: 3 + (5 + 2) = (3 + 5) + 2.

Inom en grupp kan du ibland hitta mindre uppsättningar som uppfyller alla gruppegenskaper. Om du till exempel lägger till två jämna tal får du ytterligare ett jämnt tal. De jämna talen är en grupp för sig själva, vilket gör dem till en undergrupp av heltalen. De udda talen är däremot inte en undergrupp. Om du lägger ihop två udda nummer får du ett jämnt tal – inte i originaluppsättningen. Men du kan få alla udda nummer genom att helt enkelt lägga till 1 till varje jämnt tal. En förskjuten undergrupp som denna kallas en coset. Den har inte alla egenskaper hos en undergrupp, men den behåller strukturen i sin undergrupp på många sätt. Till exempel, precis som de jämna talen, är de udda talen jämnt fördelade.

Marton antog att om du har ett set så ringer vi A består av gruppelement vars summa inte är så mycket större än A själv, så finns det någon undergrupp — kalla det G — med särskild egendom. Flytta G några gånger för att göra cosets, och dessa cosets kommer, tillsammans, innehålla den ursprungliga uppsättningen A. Dessutom antog hon att antalet cosets inte växer mycket snabbare än storleken på summan - hon trodde att det borde relateras till en polynomfaktor, i motsats till mycket snabbare exponentiell tillväxt.

Detta kan låta som en mycket teknisk kuriosa. Men eftersom det handlar om ett enkelt test — vad händer när du lägger till bara två element i uppsättningen? — för den övergripande strukturen i en undergrupp är det mycket viktigt för matematiker och datavetare. Samma allmänna idé dyker upp när datavetare försöker kryptera meddelanden så att du kan avkoda bara lite av meddelandet i taget. Det förekommer också i probabilistiskt kontrollerbara bevis, en form av bevis som datavetare kan verifiera genom att bara kontrollera några få isolerade informationsbitar. I vart och ett av dessa fall arbetar du med bara ett par punkter i en struktur - avkodar bara några bitar från ett långt meddelande, eller verifierar en liten del av ett komplicerat bevis - och drar slutsatsen något om en större struktur på högre nivå.

"Du kan antingen låtsas att allt är en stor delmängd av en grupp," sa Tom Sanders, en före detta student av Gowers som nu är en kollega till Green's i Oxford, eller så kan du "få allt du önskade från förekomsten av många additiva tillfälligheter. Båda dessa perspektiv är användbara."

Ruzsa publicerade Martons gissningar 1999, ger henne full kredit. "Hon kom till den gissningen oberoende av mig och Freiman, och förmodligen före oss," sa han. "Det var därför jag, när jag pratade med henne, bestämde mig för att kalla det hennes gissningar." Ändå hänvisar matematiker nu till det som polynomen Freiman-Ruzsa-förmodan, eller PFR.

Nollor och ettor

Grupper, som många matematiska objekt, tar många olika former. Marton antog att hennes gissningar är sanna för alla grupper. Detta har ännu inte visat sig. Det nya dokumentet bevisar det för en viss typ av grupp, som tar som element listor med binära tal som (0, 1, 1, 1, 0). Eftersom datorer fungerar binärt är denna grupp avgörande inom datavetenskap. Men det har också varit användbart i additiv kombinatorik. "Det är som den här leksaksinställningen där du kan leka och prova saker," sa Sanders. "Algebra är mycket, mycket trevligare" än att arbeta med heltal, tillade han.

Listorna har fasta längder, och varje bit kan vara antingen 0 eller 1. Du lägger ihop dem genom att lägga till varje post till sin motsvarighet i en annan lista, med regeln att 1 + 1 = 0. Så (0, 1, 1, 1 , 0) + (1, 1, 1, 1, 1) = (1, 0, 0, 0, 1). PFR är ett försök att ta reda på hur en uppsättning kan se ut om den inte riktigt är en undergrupp men har några gruppliknande egenskaper.

För att göra PFR exakt, föreställ dig att du har en uppsättning binära listor som kallas A. Ta nu varje par av element från A och lägg ihop dem. De resulterande summorna utgör summan av A, Som kallas A + A. Om elementen i A väljs slumpmässigt, då skiljer sig de flesta summorna från varandra. Om det finns k element i A, det betyder att det kommer att finnas runt k²/2 element i summamängden. När k är stor - säg 1,000 XNUMX - k²/2 är mycket större än k. Men om A är en undergrupp, varje del av A + A är A, betyder att A + A är samma storlek som A själv.

PFR betraktar mängder som inte är slumpmässiga, men inte heller är undergrupper. I dessa uppsättningar är antalet element i A + A är något litet - säg 10kEller 100k. "Det är verkligen användbart när din uppfattning om struktur är mycket rikare än att bara vara en exakt algebraisk struktur," sa Shachar Lovett, en datavetare vid University of California, San Diego.

Alla uppsättningar matematiker kände till som lydde den här egenskapen "är ganska nära faktiska undergrupper", sa Tao. "Det var intuitionen, att det inte fanns någon annan sorts falska grupper som låg runt." Freiman hade bevisat en version av detta uttalande i sitt ursprungliga verk. 1999 utökade Ruzsa Freimans teorem från heltal till inställningen av binära listor. Han bevisade att när antalet element i A + A är en konstant multipel av storleken på A, A ingår i en undergrupp.

Men Ruzsas teorem krävde att undergruppen var enorm. Martons insikt var att anföra det snarare än att vara innesluten i en gigantisk undergrupp, A kan ingå i ett polynomantal bimängder i en undergrupp som inte är större än den ursprungliga mängden A.

"Jag vet en riktig idé när jag ser en riktig idé"

Runt millennieskiftet kom Gowers över Ruzsas bevis på Freimans teorem medan han studerade ett annat problem om mängder som innehåller strängar med jämnt fördelade tal. "Jag behövde något sånt här, typ av att få strukturell information från mycket lösare information om en viss uppsättning," sa Gowers. "Jag var väldigt lyckligt lottad att Ruzsa inte så länge innan producerade detta helt underbara bevis."

Gowers började arbeta fram ett potentiellt bevis för polynomversionen av gissningen. Hans idé var att börja med ett set A vars summa var relativt liten, manipulera sedan gradvis A in i en undergrupp. Om han kunde bevisa att den resulterande undergruppen liknade den ursprungliga uppsättningen A, kunde han lätt dra slutsatsen att gissningen var sann. Gowers delade sina idéer med kollegor, men ingen kunde forma dem till ett fullständigt bevis. Även om Gowers strategi var framgångsrik i vissa fall, tog manipulationerna i andra A längre bort från den önskade slutsatsen av polynomet Freiman-Ruzsa-förmodan.

Så småningom gick fältet vidare. 2012 Sanders nästan bevisat PFR. Men antalet förskjutna undergrupper han behövde var över polynomnivån, men bara en liten bit. "När han gjorde det, betydde det att det blev en mindre brådskande sak, men fortfarande ett riktigt trevligt problem som jag har en stor förkärlek för," sa Gowers.

Men Gowers idéer levde kvar i hans kollegors minnen och hårddiskar. "Det finns en verklig idé där," sa Green, som också hade studerat Gowers. "Jag vet en riktig idé när jag ser en riktig idé." I somras befriade Green, Manners och Tao äntligen Gowers idéer från skärselden.

Green, Tao och Manners var 37 sidor djupa i samarbete innan de tänkte återgå till Gowers 20-åriga idéer. I en 23 juni papper, hade de framgångsrikt använt ett begrepp från sannolikhetsteorin som kallas slumpvariabler för att undersöka strukturen av mängder med små summängder. Genom att göra detta byte kunde gruppen manipulera sina set med mer finess. "Att hantera slumpmässiga variabler är på något sätt mycket mindre stel än att hantera uppsättningar," sa Manners. Med en slumpvariabel, "Jag kan justera en av sannolikheterna med en liten mängd, och det kan ge mig en bättre slumpvariabel."

Med detta probabilistiska perspektiv kunde Green, Manners och Tao gå från att arbeta med antalet element i en uppsättning till ett mått på informationen som finns i en slumpmässig variabel, en storhet som kallas entropi. Entropi var inte nytt för additiv kombinatorik. Faktum är att Tao hade försökt att popularisera konceptet i slutet av 2000-talet. Men ingen hade ännu försökt använda den på polynomen Freiman-Ruzsa-förmodan. Green, Manners och Tao upptäckte att det var kraftfullt. Men de kunde fortfarande inte bevisa gissningen.

När gruppen tuggade på sina nya resultat insåg de att de äntligen hade byggt en miljö där Gowers vilande idéer kunde blomstra. Om de mätte storleken på en uppsättning med hjälp av dess entropi, snarare än dess antal element, kan de tekniska detaljerna fungera mycket bättre. "Vid någon tidpunkt insåg vi att dessa gamla idéer från Tim från 20 år sedan faktiskt var mer benägna att fungera än de vi försökte," sa Tao. "Och så tog vi Tim tillbaka in i projektet. Och då passar alla bitar förvånansvärt fint ihop.”

Ändå fanns det många detaljer att ta reda på innan ett bevis kom ihop. "Det var lite dumt att vi alla fyra var otroligt upptagna med andra saker," sa Manners. "Du vill publicera det här fantastiska resultatet och berätta för världen, men du måste faktiskt fortfarande skriva dina mellanterminer." Så småningom slog gruppen igenom och den 9 november lade de ut sin tidning. De bevisade att om A + A är inte större än k gånger storleken på Aoch sedan A kan täckas av högst ca k¹² skift av en undergrupp som inte är större än A. Detta är ett potentiellt enormt antal skift. Men det är ett polynom, så det växer inte exponentiellt snabbare än k blir större, som det skulle göra om k var i exponenten.

Några dagar senare, Tao började att formalisera beviset. Han drev formaliseringsprojektet tillsammans och använde versionskontrollpaketet GitHub för att koordinera bidrag från 25 volontärer runt om i världen. De använde ett verktyg som heter Blueprint utvecklad av Patrick Massot, en matematiker vid Paris-Saclay University, för att organisera ansträngningarna att översätta från vad Tao kallas "Matematisk engelska" till datorkod. Blueprint kan bland annat skapa en diagrammet skildrar de olika logiska stegen som är involverade i bevisningen. När alla bubblor väl var täckta av vad Tao kallade en "ljuvlig nyans av grönt", var teamet klart. De upptäckte några mycket mindre stavfel i tidningen - i en online meddelande, noterade Tao att "de mest matematiskt intressanta delarna av projektet var relativt enkla att formalisera, men det var de tekniska "uppenbara" stegen som tog längst tid."

Marton dog bara några år innan hennes berömda gissning bevisades, men beviset ekar henne livsverk om entropi och informationsteori. "Allt fungerar mycket bättre när du gör det i det här entropiramverket än i det ramverk jag försökte göra det," sa Gowers. "För mig verkar det fortfarande något magiskt."

Quanta genomför en serie undersökningar för att bättre betjäna vår publik. Ta vår matematikläsarundersökning och du kommer att delta för att vinna gratis Quanta merch.