'A-Team' of Math beviser en kritisk forbindelse mellem tilføjelse og sæt | Quanta Magasinet

I et tilfældigt valgt sæt tal kan addition gå vildt.

Læg hvert par fra sådan et sæt sammen, og du ender med en ny liste, der sandsynligvis vil have mange flere tal, end du startede med. Start med 10 tilfældige tal, og denne nye liste (kaldet sumsættet) vil have omkring 50 elementer. Start med 100, og summen vil sandsynligvis have omkring 5,000; 1,000 tilfældige begyndelsestal vil gøre en summængde 500,000 lang.

Men hvis dit indledende sæt har struktur, kan sumsættet ende med færre tal end dette. Overvej et andet 10-talssæt: alle de lige tal fra 2 til 20. Fordi forskellige par vil lægge sammen til det samme tal - 10 + 12 er det samme som 8 + 14 og 6 + 16 - har sumsættet kun 19 tal, ikke 50. Denne forskel bliver mere og mere dybtgående, efterhånden som sættene bliver større. En struktureret liste med 1,000 numre kan have en summængde med kun 2,000 numre i sig.

I 1960'erne hed en matematiker Gregory Freiman begyndte at undersøge mængder med små mængder i et forsøg på at undersøge sammenhængen mellem addition og mængdestruktur - en afgørende forbindelse, der definerer det matematiske felt af additiv kombinatorik. Freiman gjorde imponerende fremskridt og beviste, at et sæt med en lille sumset skal indeholdes af et større sæt, hvis elementer er fordelt i et meget regelmæssigt mønster. Men så stagnerede feltet. "Freimans originale bevis var ekstraordinært svært at forstå, til det punkt, hvor ingen virkelig var helt sikre på, at det var korrekt. Så det havde ikke rigtig den effekt, som det kunne have haft,” sagde Timothy Gowers, en matematiker ved Collège de France og University of Cambridge og en Fields-medaljevinder. "Men derefter Imre Ruzsa bragede ind på scenen."

I en serie af to papirer i 1990'erne genbeviste Ruzsa Freimans teorem med et elegant nyt argument. Et par år senere, Katalin Marton, en indflydelsesrig ungarsk matematiker, der døde i 2019, justerede spørgsmålet om, hvad en lille summen indebærer om strukturen af ​​det originale sæt. Hun erstattede de typer elementer, der optrådte i sættet, og den type struktur, som matematikere skulle kigge efter, og troede, at det ville give matematikere mulighed for at udtrække endnu mere information. Martons formodning har links til bevissystemer, kodningsteori og kryptografi og indtager en ophøjet plads i additiv kombinatorik.

Hendes formodning "føles virkelig som en af ​​de mest grundlæggende ting, som vi ikke forstod," sagde Ben Grøn, matematiker ved University of Oxford. Det "underbyggede bare en masse ting, som jeg holder af."

Green gik sammen med Gowers, Freddie Manners fra University of California, San Diego, og Terence tao, en Fields-medaljevinder ved University of California, Los Angeles for at danne, hvad den israelske matematiker og blogger Gil Kalai kaldet en "Et hold” af matematikere. De beviste en version af formodningen i et papir delt den 9. november.

Nets Katz, en matematiker ved Rice University, som ikke var involveret i arbejdet, beskriver beviset som "smukt ligetil" - og "mere eller mindre helt ude af det blå."

Tao startede derefter et forsøg på at formalisere beviset Lean, et programmeringssprog, der hjælper matematikere med at verificere teoremer. På få uger lykkedes det. Tidligt tirsdag morgen den 5. december, Meddelte Tao at Lean havde bevist formodningen uden nogen "undskyld" - standarderklæringen, der vises, når computeren ikke kan bekræfte et bestemt trin. Dette er den højest profilerede brug af sådanne verifikationsværktøjer siden 2021, og markerer et bøjningspunkt i den måde, matematikere skriver beviser på i vendinger, som en computer kan forstå. Hvis disse værktøjer bliver nemme nok for matematikere at bruge, kan de muligvis erstatte den ofte langvarige og besværlige peer review-proces, sagde Gowers.

Bevisets ingredienser havde ulmet i årtier. Gowers udtænkte sine første skridt i begyndelsen af ​​2000'erne. Men det tog 20 år at bevise, hvad Kalai kaldte "en hellig gral" af feltet.

In-Gruppen

For at forstå Martons formodning hjælper det at være bekendt med begrebet en gruppe, et matematisk objekt, der består af et sæt og en operation. Tænk på heltal - et uendeligt sæt tal - og additionsoperationen. Hver gang du lægger to heltal sammen, får du endnu et heltal. Addition overholder også et par andre regler for gruppeoperationer, såsom associativitet, som lader dig ændre rækkefølgen af ​​operationer: 3 + (5 + 2) = (3 + 5) + 2.

Inden for en gruppe kan du nogle gange finde mindre sæt, der opfylder alle gruppeegenskaberne. Hvis du f.eks. tilføjer to lige tal, får du endnu et lige tal. De lige tal er en gruppe for sig selv, hvilket gør dem til en undergruppe af de heltal. De ulige tal er derimod ikke en undergruppe. Hvis du lægger to ulige tal sammen, får du et lige tal - ikke i det originale sæt. Men du kan få alle de ulige tal ved blot at tilføje 1 til hvert lige tal. En forskudt undergruppe som denne kaldes en coset. Den har ikke alle egenskaberne for en undergruppe, men den bevarer strukturen af ​​sin undergruppe på mange måder. For eksempel, ligesom de lige tal, er de ulige tal alle lige fordelt.

Marton formodede, at hvis du har et sæt, så ringer vi til A består af gruppeelementer, hvis summen ikke er så meget større end A sig selv, så eksisterer der en eller anden undergruppe - kald det G — med en særlig ejendom. Flytte G et par gange for at lave cosets, og disse cosets vil tilsammen indeholde det originale sæt A. Desuden antog hun, at antallet af cosets ikke vokser meget hurtigere end størrelsen af ​​sumsættet - hun mente, at det burde være relateret af en polynomiel faktor, i modsætning til meget hurtigere eksponentiel vækst.

Dette lyder måske som en meget teknisk kuriosum. Men fordi det vedrører en simpel test - hvad sker der, når du kun tilføjer to elementer i sættet? — for den overordnede struktur af en undergruppe er det meget vigtigt for matematikere og dataloger. Den samme generelle idé dukker op, når dataloger forsøger at kryptere meddelelser, så du kan afkode bare en smule af meddelelsen ad gangen. Det optræder også i probabilistisk kontrollerbare beviser, en form for bevis, som dataloger kan verificere ved kun at kontrollere nogle få isolerede informationsbidder. I hvert af disse tilfælde arbejder du kun med et par punkter i en struktur - afkodning af blot et par stykker fra en lang besked eller verificering af en lille del af et kompliceret bevis - og konkluderer noget om en større struktur på højere niveau.

"Du kan enten lade som om, alt er en stor delmængde af en gruppe," sagde Tom Sanders, en tidligere elev af Gowers, som nu er en kollega til Green's i Oxford, eller du kan "få alt, hvad du ønskede fra eksistensen af ​​mange additive tilfældigheder. Begge disse perspektiver er nyttige."

Ruzsa offentliggjorde Martons formodning i 1999, hvilket giver hende fuld kredit. "Hun kom til den formodning uafhængigt af mig og Freiman, og sandsynligvis før os," sagde han. "Det var derfor, da jeg talte med hende, besluttede jeg at kalde det hendes formodning." Alligevel refererer matematikere nu til det som polynomiet Freiman-Ruzsa formodning eller PFR.

Nuller og enere

Grupper har, ligesom mange matematiske objekter, mange forskellige former. Marton formodede, at hendes formodning er sand for alle grupper. Dette er endnu ikke vist. Det nye papir beviser det for en bestemt type gruppe, som tager som sine elementer lister over binære tal som (0, 1, 1, 1, 0). Fordi computere arbejder binært, er denne gruppe afgørende inden for datalogi. Men det har også været nyttigt i additiv kombinatorik. "Det er ligesom denne legetøjsindstilling, hvor du kan lege og prøve ting," sagde Sanders. "Algebraen er meget, meget bedre" end at arbejde med hele tal, tilføjede han.

Listerne har faste længder, og hver bit kan være enten 0 eller 1. Du lægger dem sammen ved at tilføje hver post til dens modstykke i en anden liste, med reglen om, at 1 + 1 = 0. Så (0, 1, 1, 1 , 0) + (1, 1, 1, 1, 1) = (1, 0, 0, 0, 1). PFR er et forsøg på at finde ud af, hvordan et sæt kan se ud, hvis det ikke er helt en undergruppe, men har nogle gruppelignende funktioner.

For at gøre PFR præcis, forestil dig, at du har et sæt binære lister kaldet A. Tag nu hvert par elementer fra A og læg dem sammen. De resulterende summer udgør summen af A, Kaldet A + A. Hvis elementerne i A er valgt tilfældigt, så er de fleste af summerne forskellige fra hinanden. Hvis der er k elementer i A, det betyder, at der vil være omkring k²/2 elementer i sumsættet. Hvornår k er stor - siger 1,000 - k²/2 er meget større end k. Men hvis A er en undergruppe, hvert element af A + A er i A, hvilket betyder det A + A er samme størrelse som A Selv.

PFR betragter sæt, der ikke er tilfældige, men som heller ikke er undergrupper. I disse sæt er antallet af elementer i A + A er noget lille - siger 10kEller 100k. "Det er virkelig nyttigt, når din forestilling om struktur er meget mere rig end blot at være en nøjagtig algebraisk struktur," sagde Shachar Lovett, en datalog ved University of California, San Diego.

Alle de sæt matematikere kendte til, der adlød denne egenskab "er temmelig tæt på faktiske undergrupper," sagde Tao. "Det var intuitionen, at der ikke var nogen anden form for falske grupper, der lå rundt omkring." Freiman havde bevist en version af denne erklæring i sit originale værk. I 1999 udvidede Ruzsa Freimans teorem fra heltal til indstilling af binære lister. Han beviste at når antallet af elementer i A + A er et konstant multiplum af størrelsen af A, A er indeholdt i en undergruppe.

Men Ruzsas sætning krævede, at undergruppen var enorm. Martons indsigt var at påstå det snarere end at være indeholdt i en kæmpe undergruppe, A kunne være indeholdt i et polynomielt antal cosets af en undergruppe, der ikke er større end den oprindelige mængde A.

'Jeg kender en rigtig idé, når jeg ser en rigtig idé'

Omkring årtusindskiftet stødte Gowers på Ruzsas beviser for Freimans sætning, mens han studerede et andet problem om mængder, der indeholder strenge med lige store tal. "Jeg havde brug for noget som dette, en slags at få strukturel information fra meget løsere information om et bestemt sæt," sagde Gowers. "Jeg var meget heldig, at Ruzsa ikke så længe før producerede dette helt fantastiske bevis."

Gowers begyndte at udarbejde et potentielt bevis for polynomiets version af formodningen. Hans idé var at starte med et sæt A hvis summen var relativt lille, derefter gradvist manipulere A ind i en undergruppe. Hvis han kunne bevise, at den resulterende undergruppe lignede det originale sæt A, kunne han nemt konkludere, at formodningen var sand. Gowers delte sine ideer med kolleger, men ingen kunne forme dem til et fuldstændigt bevis. Selvom Gowers' strategi var vellykket i nogle tilfælde, tog manipulationerne i andre tilfælde A længere væk fra den ønskede konklusion af polynomiet Freiman-Ruzsa formodning.

Til sidst gik feltet videre. I 2012, Sanders næsten bevist PFR. Men antallet af forskudte undergrupper, han havde brug for, var over polynomieniveauet, dog kun en lille smule. "Når han gjorde det, betød det, at det blev en mindre presserende ting, men stadig et rigtig godt problem, som jeg har en stor forkærlighed for," sagde Gowers.

Men Gowers' ideer levede videre i hans kollegers erindringer og harddiske. "Der er en rigtig idé der," sagde Green, som også havde været elev af Gowers. "Jeg kender en rigtig idé, når jeg ser en rigtig idé." Denne sommer befriede Green, Manners og Tao endelig Gowers' ideer fra deres skærsild.

Green, Tao og Manners var 37 sider dybt i samarbejde, før de tænkte på at vende tilbage til Gowers' 20 år gamle ideer. I en 23. juni papir, havde de med succes brugt et begreb fra sandsynlighedsteori kaldet tilfældige variable til at sondere strukturen af ​​mængder med små summængder. Ved at foretage dette skifte kunne gruppen manipulere deres sæt med mere finesse. "At håndtere tilfældige variabler er på en eller anden måde meget mindre stiv end at beskæftige sig med sæt," sagde Manners. Med en tilfældig variabel: "Jeg kan justere en af ​​sandsynligheden med en lille mængde, og det kan måske give mig en bedre tilfældig variabel."

Ved at bruge dette probabilistiske perspektiv kunne Green, Manners og Tao gå fra at arbejde med antallet af elementer i et sæt til en måling af informationen indeholdt i en tilfældig variabel, en størrelse kaldet entropi. Entropi var ikke nyt inden for additiv kombinatorik. Faktisk Tao havde forsøgt at popularisere konceptet i slutningen af ​​2000'erne. Men ingen havde endnu forsøgt at bruge det på polynomiet Freiman-Ruzsa formodning. Green, Manners og Tao opdagede, at det var kraftfuldt. Men de kunne stadig ikke bevise formodningen.

Mens gruppen tyggede på deres nye resultater, indså de, at de endelig havde bygget et miljø, hvor Gowers' sovende ideer kunne blomstre. Hvis de målte størrelsen af ​​et sæt ved hjælp af dets entropi, snarere end dets antal elementer, kan de tekniske detaljer fungere meget bedre. "På et tidspunkt indså vi, at disse gamle ideer fra Tim for 20 år siden faktisk var mere tilbøjelige til at virke end dem, vi prøvede," sagde Tao. "Og så vi bragte Tim tilbage i projektet. Og så passer alle brikkerne overraskende fint sammen.”

Alligevel var der mange detaljer at finde ud af, før et bevis kom sammen. "Det var lidt tåbeligt, at vi alle fire havde utrolig travlt med andre ting," sagde Manners. "Du ønsker at offentliggøre dette fantastiske resultat og fortælle verden, men du skal faktisk stadig skrive dine midtvejs." Til sidst trængte gruppen igennem, og den 9. november lagde de deres papir op. De beviste, at hvis A + A er ikke større end k gange størrelsen af A, derefter A kan højst dækkes af ca k¹² skift af en undergruppe, der ikke er større end A. Dette er potentielt et enormt antal skift. Men det er et polynomium, så det vokser ikke eksponentielt hurtigere som k bliver større, som det ville gøre hvis k var i eksponenten.

Et par dage senere, Tao begyndte at formalisere beviset. Han kørte formaliseringsprojektet i samarbejde ved at bruge versionskontrolpakken GitHub til at koordinere bidrag fra 25 frivillige rundt om i verden. De brugte et værktøj kaldet Blueprint udviklet af Patrick Massot, en matematiker ved Paris-Saclay University, for at organisere bestræbelserne på at oversætte fra det Tao kaldet "Matematisk engelsk" til computerkode. Blueprint kan blandt andet skabe en kortlægge skildrer de forskellige logiske trin involveret i beviset. Da alle boblerne var dækket af, hvad Tao kaldte en "dejlig nuance af grøn", var holdet færdige. De opdagede et par meget mindre stavefejl i avisen - i en online besked, bemærkede Tao, at "de mest matematisk interessante dele af projektet var relativt ligetil at formalisere, men det var de tekniske 'åbenlyse' trin, der tog længst."

Marton døde kun få år før hendes berømte formodning blev bevist, men beviset gentager hende livsværk om entropi og informationsteori. "Alt fungerer meget bedre, når du gør det i denne entropi-ramme, end i den ramme, jeg prøvede at gøre det," sagde Gowers. "For mig virker det stadig noget magisk."

Quanta gennemfører en række undersøgelser for bedre at kunne betjene vores publikum. Tag vores matematiklæserundersøgelse og du vil være med til at vinde gratis Quanta merch.