'A-Team' of Math beviser en kritisk kobling mellom addisjon og sett | Quanta Magazine

I et tilfeldig valgt sett med tall kan addisjon gå vilt.

Legg sammen hvert par fra et slikt sett, og du vil ende opp med en ny liste som sannsynligvis vil ha mye flere tall enn det du startet med. Start med 10 tilfeldige tall, og denne nye listen (kalt summen) vil ha omtrent 50 elementer. Start med 100 og summen vil trolig ha rundt 5,000; 1,000 tilfeldige innledende tall vil gjøre en summen 500,000 XNUMX tall lang.

Men hvis det første settet ditt har struktur, kan sumsettet ende opp med færre tall enn dette. Tenk på et annet 10-tallssett: alle partallene fra 2 til 20. Fordi forskjellige par vil legge sammen til samme tall — 10 + 12 er det samme som 8 + 14 og 6 + 16 — har sumsettet bare 19 tall, ikke 50. Denne forskjellen blir mer og mer dyptgripende ettersom settene blir større. En strukturert liste med 1,000 numre kan ha et sumsett med bare 2,000 numre.

På 1960-tallet het en matematiker Gregory Freiman begynte å undersøke sett med små sumsett i et forsøk på å undersøke koblingen mellom addisjon og settstruktur - en avgjørende forbindelse som definerer det matematiske feltet additiv kombinatorikk. Freiman gjorde imponerende fremskritt, og beviste at et sett med en liten summengde må inneholdes av et større sett hvis elementer er plassert i et svært regelmessig mønster. Men så stagnerte feltet. «Freimans originale bevis var usedvanlig vanskelig å forstå, til det punktet hvor ingen egentlig var helt sikre på at det var riktig. Så det hadde egentlig ikke den innvirkningen det kunne ha hatt," sa Timothy Gowers, en matematiker ved Collège de France og University of Cambridge og en Fields-medaljevinner. "Men da Imre Ruzsa sprang inn på scenen."

I en serie av to papirer på 1990-tallet beviste Ruzsa Freimans teorem på nytt med et elegant nytt argument. Noen år senere, Katalin Marton, en innflytelsesrik ungarsk matematiker som døde i 2019, finjusterte spørsmålet om hva en liten sum betyr om strukturen til det originale settet. Hun erstattet typene elementer som dukket opp i settet og typen struktur som matematikere burde se etter, og tenkte at det ville tillate matematikere å trekke ut enda mer informasjon. Martons formodning har koblinger til bevissystemer, kodingsteori og kryptografi, og inntar en opphøyet plass i additiv kombinatorikk.

Formodningen hennes "føles virkelig som en av de mest grunnleggende tingene vi ikke forsto," sa Ben Green, en matematiker ved University of Oxford. Det "bare på en måte underbygget mange ting jeg bryr meg om."

Green slo seg sammen med Gowers, Freddie Manners fra University of California, San Diego, og Terence tao, en Fields-medaljevinner ved University of California, Los Angeles for å danne det den israelske matematikeren og bloggeren Gil Kalai kalt en "Et lag" av matematikere. De beviste en versjon av formodningen i et papir delt 9. november.

Nets Katz, en matematiker ved Rice University som ikke var involvert i arbeidet, beskriver beviset som "vakkert enkelt" - og "mer eller mindre helt ut av det blå."

Tao startet deretter et forsøk på å formalisere beviset Lene, et programmeringsspråk som hjelper matematikere å verifisere teoremer. På bare noen få uker lyktes den innsatsen. Tidlig tirsdag morgen 5. desember, Tao annonserte at Lean hadde bevist formodningen uten noen "beklager" - standardutsagnet som vises når datamaskinen ikke kan bekrefte et bestemt trinn. Dette er den høyest profilerte bruken av slike verifiseringsverktøy siden 2021, og markerer et bøyningspunkt i måten matematikere skriver bevis på i termer en datamaskin kan forstå. Hvis disse verktøyene blir enkle nok for matematikere å bruke, kan de kanskje erstatte den ofte langvarige og tyngende fagfellevurderingsprosessen, sa Gowers.

Ingrediensene til beviset hadde putret i flere tiår. Gowers unnfanget sine første skritt på begynnelsen av 2000-tallet. Men det tok 20 år å bevise det Kalai kalte "en hellig gral" av feltet.

In-Gruppen

For å forstå Martons formodning hjelper det å være kjent med begrepet en gruppe, et matematisk objekt som består av et sett og en operasjon. Tenk på heltallene – et uendelig sett med tall – og addisjonsoperasjonen. Hver gang du legger to heltall sammen, får du et nytt heltall. Addisjon følger også noen få andre regler for gruppeoperasjoner, som assosiativitet, som lar deg endre rekkefølgen av operasjoner: 3 + (5 + 2) = (3 + 5) + 2.

Innenfor en gruppe kan du noen ganger finne mindre sett som tilfredsstiller alle gruppeegenskapene. Hvis du for eksempel legger til to partall, får du et annet partall. Partallene er en gruppe for seg selv, noe som gjør dem til en undergruppe av heltallene. Oddetallene er derimot ikke en undergruppe. Hvis du legger sammen to oddetall, får du et partall – ikke i det opprinnelige settet. Men du kan få alle oddetallene ved å legge til 1 til hvert partall. En forskjøvet undergruppe som dette kalles en coset. Den har ikke alle egenskapene til en undergruppe, men den beholder strukturen til undergruppen på mange måter. For eksempel, akkurat som partall, er alle oddetall jevnt fordelt.

Marton mente at hvis du har et sett så ringer vi A består av gruppeelementer hvis summen ikke er så mye større enn A seg selv, så eksisterer det en undergruppe - kall det G — med en spesiell eiendom. Skifte G et par ganger for å lage cosets, og disse cosets vil, tatt sammen, inneholde det originale settet A. Dessuten antok hun at antallet cosets ikke vokser mye raskere enn størrelsen på summen - hun mente det burde være relatert til en polynomfaktor, i motsetning til mye raskere eksponentiell vekst.

Dette kan høres ut som en svært teknisk kuriositet. Men fordi det relaterer seg til en enkel test - hva skjer når du bare legger til to elementer i settet? — for den overordnede strukturen til en undergruppe er det svært viktig for matematikere og informatikere. Den samme generelle ideen dukker opp når dataforskere prøver å kryptere meldinger slik at du kan dekode bare litt av meldingen om gangen. Det dukker også opp i probabilistisk kontrollerbare bevis, en form for bevis som informatikere kan verifisere ved å sjekke bare noen få isolerte informasjonsbiter. I hvert av disse tilfellene jobber du med bare et par punkter i en struktur – dekoder bare noen få biter fra en lang melding, eller verifiserer en liten del av et komplisert bevis – og konkluderer med noe om en større struktur på høyere nivå.

"Du kan enten late som om alt er en stor undergruppe av en gruppe," sa Tom Sanders, en tidligere student ved Gowers som nå er en kollega av Green's i Oxford, eller du kan "få alt du ønsket fra eksistensen av mange additive tilfeldigheter. Begge disse perspektivene er nyttige.»

Ruzsa publiserte Martons formodning i 1999, og gir henne full ære. "Hun kom til den formodningen uavhengig av meg og Freiman, og sannsynligvis før oss," sa han. "Derfor, da jeg snakket med henne, bestemte jeg meg for å kalle det hennes formodning." Likevel omtaler matematikere det nå som polynomen Freiman-Ruzsa-formodningen, eller PFR.

Nuller og en

Grupper, som mange matematiske objekter, har mange forskjellige former. Marton antok at formodningen hennes er sann for alle grupper. Dette er ennå ikke vist. Det nye papiret beviser det for en bestemt type gruppe, som tar som sine elementer lister over binære tall som (0, 1, 1, 1, 0). Fordi datamaskiner fungerer binært, er denne gruppen avgjørende innen informatikk. Men det har også vært nyttig i additiv kombinatorikk. "Det er som denne lekesettingen der du kan leke og prøve ting," sa Sanders. "Algebraen er mye, mye bedre" enn å jobbe med hele tall, la han til.

Listene har faste lengder, og hver bit kan være enten 0 eller 1. Du legger dem sammen ved å legge hver oppføring til sin motpart i en annen liste, med regelen at 1 + 1 = 0. Så (0, 1, 1, 1 , 0) + (1, 1, 1, 1, 1) = (1, 0, 0, 0, 1). PFR er et forsøk på å finne ut hvordan et sett kan se ut hvis det ikke er en undergruppe, men har noen gruppelignende funksjoner.

For å gjøre PFR presis, forestill deg at du har et sett med binære lister kalt A. Ta nå hvert par av elementer fra A og legge dem sammen. De resulterende summene utgjør summen av A, Kalt A + A. Hvis elementene i A velges tilfeldig, da er de fleste summene forskjellige fra hverandre. Hvis det er k elementer i A, det betyr at det vil være rundt k²/2 elementer i summen. Når k er stor - si 1,000 - k²/2 er mye større enn k. Men hvis A er en undergruppe, hvert element av A + A er i A, som betyr at A + A er samme størrelse som A selv.

PFR vurderer sett som ikke er tilfeldige, men heller ikke er undergrupper. I disse settene er antallet elementer i A + A er litt liten - si 10k, Eller 100k. "Det er veldig nyttig når forestillingen om struktur er mye mer rik enn bare å være en eksakt algebraisk struktur," sa Shachar Lovett, en informatiker ved University of California, San Diego.

Alle settene matematikere visste om som adlød denne egenskapen "er ganske nær faktiske undergrupper," sa Tao. "Det var intuisjonen, at det ikke var noen andre slags falske grupper som lå rundt." Freiman hadde bevist en versjon av denne uttalelsen i sitt originale arbeid. I 1999 utvidet Ruzsa Freimans teorem fra heltallene til innstillingen av binære lister. Han beviste at når antall elementer i A + A er et konstant multiplum av størrelsen på A, A er inneholdt i en undergruppe.

Men Ruzsas teorem krevde at undergruppen var enorm. Martons innsikt var å antyde det i stedet for å være inneholdt i en gigantisk undergruppe, A kan være inneholdt i et polynomantall av kosett i en undergruppe som ikke er større enn det opprinnelige settet A.

"Jeg vet en ekte idé når jeg ser en ekte idé"

Rundt årtusenskiftet kom Gowers over Ruzsas bevis på Freimans teorem mens han studerte et annet problem om sett som inneholder strenger med jevnt fordelte tall. "Jeg trengte noe sånt som dette, på en måte å få strukturell informasjon fra mye løsere informasjon om et bestemt sett," sa Gowers. "Jeg var veldig heldig som ikke så lenge før, Ruzsa produserte dette helt nydelige beviset."

Gowers begynte å utarbeide et potensielt bevis for polynomversjonen av formodningen. Ideen hans var å starte med et sett A hvis summen var relativt liten, deretter gradvis manipulere A inn i en undergruppe. Hvis han kunne bevise at den resulterende undergruppen var lik det originale settet A, kunne han lett konkludere med at formodningen var sann. Gowers delte ideene sine med kolleger, men ingen kunne forme dem til et fullstendig bevis. Selv om Gowers strategi var vellykket i noen tilfeller, tok manipulasjonene i andre A lenger unna den ønskede konklusjonen til polynomet Freiman-Ruzsa-formodningen.

Etter hvert gikk feltet videre. I 2012, Sanders nesten bevist PFR. Men antallet forskjøvede undergrupper han trengte var over polynomnivået, men bare litt. "Når han gjorde det, betydde det at det ble en mindre presserende ting, men fortsatt et veldig fint problem som jeg har en stor forkjærlighet for," sa Gowers.

Men Gowers ideer levde videre i kollegenes minner og harddisker. "Det er en virkelig idé der," sa Green, som også hadde vært elev av Gowers. "Jeg vet en ekte idé når jeg ser en ekte idé." Denne sommeren frigjorde Green, Manners og Tao endelig Gowers ideer fra skjærsilden deres.

Green, Tao og Manners var 37 sider dypt i samarbeid før de tenkte å gå tilbake til Gowers' 20 år gamle ideer. I en 23. juni papir, hadde de med hell brukt et konsept fra sannsynlighetsteori kalt tilfeldige variabler for å undersøke strukturen til sett med små sumsett. Ved å gjøre denne overgangen kunne gruppen manipulere settene sine med mer finesse. "Å håndtere tilfeldige variabler er på en eller annen måte mye mindre rigid enn å håndtere sett," sa Manners. Med en tilfeldig variabel, "jeg kan justere en av sannsynlighetene med en liten mengde, og det kan gi meg en bedre tilfeldig variabel."

Ved å bruke dette sannsynlighetsperspektivet kunne Green, Manners og Tao gå fra å jobbe med antall elementer i et sett til en måling av informasjonen i en tilfeldig variabel, en mengde som kalles entropi. Entropi var ikke nytt for additiv kombinatorikk. Faktisk Tao hadde forsøkt å popularisere konseptet på slutten av 2000-tallet. Men ingen hadde ennå prøvd å bruke det på polynomet Freiman-Ruzsa-formodningen. Green, Manners og Tao oppdaget at den var kraftig. Men de kunne fortsatt ikke bevise formodningen.

Mens gruppen tygget på de nye resultatene, innså de at de endelig hadde bygget et miljø der Gowers' sovende ideer kunne blomstre. Hvis de målte størrelsen på et sett ved å bruke dets entropi, i stedet for antall elementer, kan de tekniske detaljene fungere mye bedre. "På et tidspunkt innså vi at disse gamle ideene fra Tim for 20 år siden faktisk var mer sannsynlige for å fungere enn de vi prøvde," sa Tao. "Og så vi tok Tim tilbake inn i prosjektet. Og så passer alle brikkene overraskende fint sammen.»

Likevel var det mange detaljer å finne ut før et bevis kom sammen. "Det var litt dumt at vi alle fire var utrolig opptatt med andre ting," sa Manners. "Du ønsker å publisere dette flotte resultatet og fortelle verden, men du må faktisk fortsatt skrive midtveis." Til slutt presset gruppen gjennom, og 9. november la de ut papiret sitt. De beviste at hvis A + A er ikke større enn k ganger størrelsen på A, deretter A kan dekkes av ikke mer enn ca k¹² skift av en undergruppe som ikke er større enn A. Dette er potensielt et enormt antall skift. Men det er et polynom, så det vokser ikke eksponentielt raskere som k blir større, som det ville gjort hvis k var i eksponenten.

Noen dager senere, Tao begynte å formalisere beviset. Han drev formaliseringsprosjektet i samarbeid, ved å bruke versjonskontrollpakken GitHub for å koordinere bidrag fra 25 frivillige over hele verden. De brukte et verktøy som heter Blueprint utviklet av Patrick Massot, en matematiker ved Paris-Saclay University, for å organisere arbeidet med å oversette fra det Tao som heter "Matematisk engelsk" til datakode. Blueprint kan blant annet lage en diagram som viser de ulike logiske trinnene som er involvert i beviset. Når alle boblene var dekket av det Tao kalte en "nydelig nyanse av grønn", var teamet ferdig. De oppdaget noen få svært små skrivefeil i avisen - i en online melding, bemerket Tao at "de mest matematisk interessante delene av prosjektet var relativt enkle å formalisere, men det var de tekniske "åpenbare" trinnene som tok lengst."

Marton døde bare noen få år før hennes berømte formodning ble bevist, men beviset gjenspeiler henne livsverk om entropi og informasjonsteori. "Alt fungerer mye bedre når du gjør det i dette entropi-rammeverket enn i rammeverket jeg prøvde å gjøre det," sa Gowers. "For meg virker det fortsatt noe magisk."

Quanta gjennomfører en serie undersøkelser for å tjene publikum bedre. Ta vår matematikk leserundersøkelse og du vil bli registrert for å vinne gratis Quanta varer.