Matematiikan "A-tiimi" osoittaa kriittisen yhteyden lisäyksen ja sarjojen välillä | Quanta-lehti

Satunnaisesti valitussa numerosarjassa lisääminen voi mennä villiin.

Kun lasket yhteen tällaisen sarjan kaikki parit, päädyt uuteen luetteloon, jossa on todennäköisesti paljon enemmän numeroita kuin mitä aloitit. Aloita 10 satunnaisluvulla, ja tämä uusi luettelo (kutsutaan summajoukoksi) sisältää noin 50 elementtiä. Aloita 100:lla ja summassa on todennäköisesti noin 5,000 1,000; 500,000 XNUMX satunnaista alkulukua tekee summajoukosta XNUMX XNUMX numeroa pitkän.

Mutta jos alkujoukollasi on rakenne, summajoukossa voi olla tätä vähemmän lukuja. Harkitse toista 10-luvun joukkoa: kaikki parilliset luvut 2:sta 20:een. Koska eri parit muodostavat saman luvun — 10 + 12 on sama kuin 8 + 14 ja 6 + 16 -, summajoukossa on vain 19 numeroa, ei 50. Tämä ero tulee yhä syvemmäksi, kun joukot kasvavat. 1,000 2,000 numeron jäsennellyssä luettelossa voi olla summa, jossa on vain XNUMX XNUMX numeroa.

1960-luvulla matemaatikko nimeltä Gregory Freiman alkoi tutkia joukkoja, joissa on pieniä summia, pyrkiessään tutkimaan yhteenlasku- ja joukkorakenteen välistä yhteyttä - ratkaisevaa yhteyttä, joka määrittelee additiivisen kombinatorian matemaattisen kentän. Freiman edistyi vaikuttavasti ja osoitti, että pienen summajoukon täytyy sisältyä suurempaan joukkoon, jonka elementit ovat hyvin säännöllisin väliajoin. Mutta sitten kenttä pysähtyi. ”Freimanin alkuperäinen todistus oli äärimmäisen vaikea ymmärtää, niin pitkälle, että kukaan ei todellakaan ollut täysin varma sen oikeellisuudesta. Joten sillä ei oikeastaan ​​ollut vaikutusta, mitä sillä olisi voinut olla, sanoi Timothy Gowers, matemaatikko Collège de Francessa ja Cambridgen yliopistossa ja Fields-mitalisti. "Mutta toisaalta Imre Ruzsa ryntäsi paikalle."

Sarjassa kaksi paperit 1990-luvulla Ruzsa toisti Freimanin lauseen tyylikkäällä uudella argumentilla. Muutama vuosi myöhemmin, Katalin Marton, vuonna 2019 kuollut vaikutusvaltainen unkarilainen matemaatikko, tarkensi kysymystä siitä, mitä pieni summa merkitsee alkuperäisen joukon rakenteesta. Hän korvasi joukossa esiintyvien elementtien tyypit ja matemaatikoiden etsimän rakenteen ajatellen, että matemaatikot voisivat poimia vielä enemmän tietoa. Martonin olettamuksella on linkkejä todistusjärjestelmiin, koodausteoriaan ja kryptografiaan, ja sillä on korkea paikka additiivisessa kombinatoriikassa.

Hänen arvelunsa "tuntuu todella yhdeltä alkeellisimmista asioista, joita emme ymmärtäneet", sanoi Ben Green, matemaatikko Oxfordin yliopistosta. Se "vain tavallaan tuki monia asioita, joista välitän".

Green yhdisti voimansa Gowersin kanssa, Freddie Manners Kalifornian yliopistosta San Diegosta ja Terence tao, Fields-mitalisti Kalifornian yliopistossa Los Angelesissa muodostaen sen, mitä israelilainen matemaatikko ja bloggaaja Gil Kalai nimeltään "Tiimi” matemaatikot. He osoittivat version oletuksesta paperilla jaettu 9. marraskuuta.

Nets Katz, Ricen yliopiston matemaatikko, joka ei osallistunut työhön, kuvailee todistetta "kauniin suoraviivaiseksi" - ja "enemmän tai vähemmän täysin tyhjästä".

Tao aloitti sitten yrityksen virallistaakseen todisteen Lean, ohjelmointikieli, joka auttaa matemaatikoita vahvistamaan lauseita. Muutamassa viikossa tämä yritys onnistui. Varhain tiistaiaamuna 5. joulukuuta, Tao ilmoitti että Lean oli todistanut olettamuksen ilman "anteeksi" - vakiolausuntoa, joka ilmestyy, kun tietokone ei pysty varmistamaan tiettyä vaihetta. Tämä on tällaisten korkeimman profiilin käyttöä vahvistustyökalut vuodesta 2021 lähtien, ja merkitsee käännekohtaa tavoissa, joilla matemaatikot kirjoittavat todisteita termeillä, joita tietokone voi ymmärtää. Jos näistä työkaluista tulee tarpeeksi helppokäyttöisiä matemaatikoille, ne saattavat pystyä korvaamaan usein pitkittyneen ja työläs vertaisarviointiprosessin, Gowers sanoi.

Todistuksen ainekset olivat kypsyneet vuosikymmeniä. Gowers sai ensimmäiset askeleensa 2000-luvun alussa. Mutta kesti 20 vuotta todistaa sen, mitä Kalai kutsui pellon "pyhäksi maljaksi".

Ryhmän sisäinen

Martonin arvelun ymmärtäminen auttaa tuntemaan ryhmän käsitteen, matemaattisen objektin, joka koostuu joukosta ja operaatiosta. Ajattele kokonaislukuja – ääretöntä joukkoa lukuja – ja yhteenlaskuoperaatiota. Joka kerta kun lisäät kaksi kokonaislukua yhteen, saat toisen kokonaisluvun. Lisääminen noudattaa myös muutamia muita ryhmätoimintojen sääntöjä, kuten assosiatiivisuutta, jonka avulla voit muuttaa operaatioiden järjestystä: 3 + (5 + 2) = (3 + 5) + 2.

Ryhmän sisällä voi joskus löytää pienempiä joukkoja, jotka täyttävät kaikki ryhmän ominaisuudet. Jos esimerkiksi lisäät kaksi parillista lukua, saat toisen parillisen luvun. Parilliset luvut ovat ryhmä itselleen, mikä tekee niistä kokonaislukujen alaryhmän. Parittomat luvut eivät sitä vastoin ole alaryhmä. Jos lasket yhteen kaksi paritonta numeroa, saat parillisen luvun – ei alkuperäisessä joukossa. Mutta voit saada kaikki parittomat luvut lisäämällä 1 jokaiseen parilliseen numeroon. Tällaista siirrettyä alaryhmää kutsutaan kosetiksi. Sillä ei ole kaikkia alaryhmän ominaisuuksia, mutta se säilyttää alaryhmän rakenteen monin tavoin. Esimerkiksi, kuten parilliset luvut, parittomat luvut ovat kaikki tasaisin välein.

Marton arveli, että jos sinulla on setti, soitamme A koostuu ryhmäelementeistä, joiden summa ei ole paljon suurempi kuin A itse, silloin on olemassa jokin alaryhmä - kutsu sitä G — erityisellä omaisuudella. Siirtää G muutaman kerran koskien valmistamista varten, ja nämä paketit sisältävät yhdessä alkuperäisen sarjan A. Lisäksi hän oletti, että kosettien määrä ei kasva paljon nopeammin kuin summajoukon koko - hän uskoi, että sen pitäisi liittyä polynomitekijällä, toisin kuin paljon nopeammalla eksponentiaalisella kasvulla.

Tämä saattaa kuulostaa erittäin tekniseltä uteliaisuudelta. Mutta koska se liittyy yksinkertaiseen testiin – mitä tapahtuu, kun lisäät vain kaksi elementtiä joukkoon? — Alaryhmän kokonaisrakenteen kannalta se on erittäin tärkeä matemaatikoille ja tietojenkäsittelytieteilijöille. Sama yleinen ajatus ilmenee, kun tietojenkäsittelytieteilijät yrittävät salata viestejä, jotta voit purkaa vain osan viestistä kerrallaan. Se esiintyy myös todennäköisyydellä tarkistettavissa todisteissa, todistusmuodossa, jonka tietojenkäsittelytieteilijät voivat varmistaa tarkistamalla vain muutaman yksittäisen tiedon. Kaikissa näissä tapauksissa työskentelet vain muutaman pisteen kanssa rakenteessa – dekoodaat vain muutaman bitin pitkästä viestistä tai tarkistat pienen osan monimutkaisesta todistuksesta – ja päätät jotain suuremmasta, korkeamman tason rakenteesta.

"Voit joko teeskennellä, että kaikki on suuri osa ryhmästä", sanoi Tom Sanders, Gowersin entinen opiskelija, joka on nyt Greenin kollega Oxfordissa, tai voit saada kaiken mitä halusit monien lisäsattumien olemassaolosta. Molemmat näkökulmat ovat hyödyllisiä."

Ruzsa julkaisi Martonin olettamuksen vuonna 1999, antaen hänelle täyden tunnustuksen. "Hän tuli tuohon olettamukseen minusta ja Freimanista riippumatta ja luultavasti ennen meitä", hän sanoi. "Siksi, kun puhuin hänen kanssaan, päätin kutsua sitä hänen olettamukseksi." Silti matemaatikot kutsuvat sitä nykyään polynomi Freiman-Ruzsa-oletukseksi tai PFR:ksi.

Nollia ja yhtä

Ryhmät, kuten monet matemaattiset objektit, saavat monia eri muotoja. Marton arveli, että hänen olettamuksensa pätee kaikkiin ryhmiin. Tämä on vielä näytettävä. Uusi paperi todistaa sen tietynlaiselle ryhmälle, joka ottaa elementeiksi luettelot binääriluvuista, kuten (0, 1, 1, 1, 0). Koska tietokoneet toimivat binäärimuodossa, tämä ryhmä on tietojenkäsittelytieteen kannalta ratkaiseva. Mutta se on ollut hyödyllinen myös additiivisessa kombinatoriikassa. "Se on kuin tämä leluympäristö, jossa voit leikkiä ja kokeilla asioita", Sanders sanoi. "Algebra on paljon, paljon mukavampaa" kuin työskentely kokonaislukujen kanssa, hän lisäsi.

Listojen pituudet ovat kiinteät ja jokainen bitti voi olla joko 0 tai 1. Ne lisätään yhteen lisäämällä jokainen merkintä vastaavaan toisessa listassa säännöllä, että 1 + 1 = 0. Joten (0, 1, 1, 1 , 0) + (1, 1, 1, 1, 1) = (1, 0, 0, 0, 1). PFR on yritys selvittää, miltä joukko voi näyttää, jos se ei ole aivan alaryhmä, mutta siinä on joitain ryhmämäisiä ominaisuuksia.

PFR:n tarkentamiseksi kuvittele, että sinulla on joukko binäärilistoja nimeltä A. Ota nyt jokainen elementtipari A ja laske ne yhteen. Tuloksena saadut summat muodostavat summan A, Kutsutaan A + A. Jos elementit A valitaan satunnaisesti, silloin useimmat summat ovat erilaisia. Jos siellä on k elementit A, se tarkoittaa, että niitä on noin k²/2 elementtiä summassa. Kun k on suuri - sanotaan 1,000 - k²/2 on paljon suurempi kuin k. Mutta jos A on alaryhmä, sen jokainen elementti A + A on A, tarkoittaen sitä A + A on samankokoinen kuin A itse.

PFR ottaa huomioon joukot, jotka eivät ole satunnaisia, mutta eivät myöskään ole alaryhmiä. Näissä sarjoissa olevien elementtien määrä A + A on hieman pieni - sanotaan 10kTai 100k. "Se on todella hyödyllistä, kun käsityksesi rakenteesta on paljon rikkaampi kuin pelkkä tarkka algebrallinen rakenne", sanoi. Shachar Lovett, tietojenkäsittelytieteilijä Kalifornian yliopistosta San Diegosta.

Kaikki matemaatikot tiesivät, että tämä ominaisuus totteli, "ovat melko lähellä todellisia alaryhmiä", Tao sanoi. "Se oli intuitio, ettei siellä ollut muita valeryhmiä." Freiman oli todistanut version tästä väitteestä alkuperäisessä työssään. Vuonna 1999 Ruzsa laajensi Freimanin lauseen kokonaisluvuista binäärilistojen asettamiseen. Hän todisti että kun elementtien lukumäärä A + A on koon vakiokerrannainen A, A sisältyy alaryhmään.

Mutta Ruzsan lause vaati alaryhmän olevan valtava. Martonin näkemys oli olettaa, että sen sijaan että olisi kuulunut yhteen jättiläiseen alaryhmään, A voi sisältyä aliryhmän kosettien polynomimäärään, joka ei ole suurempi kuin alkuperäinen joukko A.

"Tiedän todellisen idean, kun näen todellisen idean"

Vuosituhannen vaihteessa Gowers törmäsi Ruzsan Freimanin lauseen todisteisiin tutkiessaan erilaista ongelmaa joukoista, jotka sisältävät tasavälisiä lukujonoja. "Tarvitsin jotain tällaista, eräänlaista rakenteellista tietoa tietystä joukosta paljon löyhemmästä tiedosta", Gowers sanoi. "Olin erittäin onnekas, että Ruzsa ei niin kauan ennen tuottanut tämän aivan upean todisteen."

Gowers alkoi kehittää mahdollista todistetta arvelun polynomiversiosta. Hänen ideansa oli aloittaa setillä A joiden summa oli suhteellisen pieni, sitten vähitellen manipuloida A alaryhmään. Jos hän pystyisi todistamaan, että tuloksena oleva alaryhmä oli samanlainen kuin alkuperäinen joukko A, hän saattoi helposti päätellä, että olettamus oli totta. Gowers jakoi ideansa kollegoilleen, mutta kukaan ei voinut muokata niitä täydelliseksi todisteeksi. Vaikka Gowersin strategia onnistui joissakin tapauksissa, toisissa manipulaatiot vaativat A kauempana polynomin Freiman-Ruzsa-oletuksen halutusta johtopäätöksestä.

Lopulta kenttä eteni. Vuonna 2012 Sanders melkein osoittautunut PFR:ksi. Mutta hänen tarvitsemansa siirtyneiden alaryhmien määrä oli polynomitason yläpuolella, vaikkakin vain vähän. "Kun hän teki sen, se tarkoitti, että siitä tuli vähemmän kiireellinen asia, mutta silti todella mukava ongelma, josta pidän suuresti", Gowers sanoi.

Mutta Gowersin ideat elivät hänen kollegoidensa muistoissa ja kiintolevyissä. "Siellä on todellinen idea", sanoi Green, joka oli myös ollut Gowersin oppilas. "Tiedän todellisen idean, kun näen todellisen idean." Tänä kesänä Green, Manners ja Tao vapauttivat vihdoin Gowersin ideat kiirastulestaan.

Green, Tao ja Manners olivat 37 sivua syvällä yhteistyössä ennen kuin he ajattelivat palata Gowersin 20 vuotta vanhoihin ideoihin. Eräänä kesäkuun 23. päivänä paperi, he olivat onnistuneesti käyttäneet todennäköisyysteorian käsitettä, jota kutsutaan satunnaismuuttujiksi, tutkiakseen joukkojen rakennetta pienillä summajouksilla. Tekemällä tämän vaihdon ryhmä voisi manipuloida sarjojaan hienostuneemmin. "Satunnaismuuttujien käsitteleminen on jotenkin paljon vähemmän jäykkää kuin joukkojen käsittely", Manners sanoi. Satunnaismuuttujan avulla "Voin säätää yhtä todennäköisyyksistä pienellä määrällä, ja se saattaa antaa minulle paremman satunnaismuuttujan."

Käyttämällä tätä todennäköisyysnäkökulmaa Green, Manners ja Tao voisivat siirtyä työskentelystä joukon elementtien lukumäärän kanssa satunnaismuuttujan sisältämän tiedon mittaamiseen, entropiaksi kutsuttuun suureen. Entropia ei ollut uutta additiiviselle kombinatoriikalle. Itse asiassa Tao oli yrittänyt konseptin popularisoimiseksi 2000-luvun lopulla. Mutta kukaan ei ollut vielä yrittänyt käyttää sitä polynomissa Freiman-Ruzsa-oletuksissa. Green, Manners ja Tao huomasivat sen olevan voimakas. Mutta he eivät silti pystyneet todistamaan olettamusta.

Kun ryhmä pureskeli uusia tuloksiaan, he ymmärsivät, että he olivat vihdoin rakentaneet ympäristön, jossa Gowersin uinuvat ideat voisivat kukoistaa. Jos he mittasivat joukon koon käyttämällä sen entropiaa, eikä sen elementtien lukumäärää, tekniset yksityiskohdat voisivat toimia paljon paremmin. "Jossain vaiheessa tajusimme, että nämä Timin 20 vuoden takaiset vanhat ideat toimivat itse asiassa todennäköisemmin kuin ne, joita yritimme", Tao sanoi. "Ja niin toimme Timin takaisin projektiin. Ja sitten kaikki palaset sopivat yhteen yllättävän kauniisti.”

Silti monia yksityiskohtia oli selvitettävä ennen kuin todisteet saatiin koolle. "Oli tavallaan typerää, että me kaikki neljä olimme uskomattoman kiireisiä muiden asioiden kanssa", Manners sanoi. "Haluat julkaista tämän hienon tuloksen ja kertoa siitä maailmalle, mutta itse asiassa sinun on silti kirjoitettava väliaikasi." Lopulta ryhmä pääsi läpi, ja 9. marraskuuta he julkaisivat paperinsa. He todistivat, että jos A + A ei ole suurempi kuin k kertaa kokoinen A, sitten A voidaan kattaa enintään noin k¹² alaryhmän siirtymät, joka ei ole suurempi kuin A. Tämä on mahdollisesti valtava määrä vuoroja. Mutta se on polynomi, joten se ei kasva eksponentiaalisesti nopeammin kuin k kasvaa isommaksi, kuin jos se olisi k olivat eksponentin sisällä.

Muutamaa päivää myöhemmin, Tao alkoi virallistaa todistus. Hän johti formalisointiprojektia yhteistyössä GitHubin versionhallintapaketin avulla koordinoimaan lahjoituksia 25 vapaaehtoista ympäri maailmaa. He käyttivät työkalua nimeltä Suunnitelma kehittämä Patrick Massot, matemaatikko Paris-Saclay-yliopistossa, organisoimaan pyrkimyksiä kääntää mitä Tao nimeltään "Matemaattinen englanti" tietokonekoodiksi. Suunnitelma voi muun muassa luoda a kartoittaa kuvaavat todistuksen eri loogisia vaiheita. Kun kaikki kuplat olivat peittyneet niin, että Tao kutsui "ihanaksi vihreän sävyksi", tiimi oli valmis. He löysivät muutamia hyvin pieniä kirjoitusvirheitä lehdestä - verkossa viesti, Tao huomautti, että "projektin matemaattisesti mielenkiintoisimmat osat olivat suhteellisen yksinkertaisia ​​muotoilla, mutta tekniset "ilmeiset" vaiheet kestivät pisimpään."

Marton kuoli vain muutama vuosi ennen kuin hänen kuuluisa olettamuksensa todistettiin, mutta todiste toistaa häntä elämäntyö entropiasta ja informaatioteoriasta. "Kaikki toimii paljon paremmin, kun teet sen tässä entropiakehyksessä kuin kehyksessä, jota yritin tehdä", Gowers sanoi. "Minusta se näyttää edelleen hieman taianomaiselta."

Quanta tekee sarjan kyselyjä palvellakseen paremmin yleisöämme. Ota meidän matematiikan lukijakysely ja pääset mukaan voittamaan ilmaiseksi Quanta kauppatavaraa.