'A-Team' matematike dokazuje ključno povezavo med seštevanjem in množicami | Revija Quanta

V naključno izbranem nizu števil lahko seštevanje podivja.

Seštejte vse pare iz takega niza in na koncu boste dobili nov seznam, ki bo verjetno vseboval veliko več številk od tistega, s katerim ste začeli. Začnite z 10 naključnimi številkami in ta novi seznam (imenovan vsota) bo imel približno 50 elementov. Začnite s 100 in vsota bo verjetno imela približno 5,000; 1,000 naključnih začetnih števil bo seštevek dolg 500,000 števil.

Toda če ima vaš začetni niz strukturo, lahko vsota na koncu vsebuje manj števil od tega. Razmislite o drugem nizu 10 števil: vsa soda števila od 2 do 20. Ker bodo različni pari sešteli isto število – 10 + 12 je enako kot 8 + 14 in 6 + 16 – ima vsota samo 19 števil, ne 50. Ta razlika postaja vedno bolj globoka, ko se sklopi povečujejo. Strukturiran seznam 1,000 številk ima lahko vsoto s samo 2,000 številkami.

V šestdesetih letih prejšnjega stoletja je matematik imenovan Gregory Freiman začel preiskovati množice z majhnimi vsotami, da bi raziskal povezavo med seštevanjem in strukturo množice – ključno povezavo, ki opredeljuje matematično polje aditivne kombinatorike. Freiman je dosegel impresiven napredek in dokazal, da mora množico z majhno vsoto vsebovati večja množica, katere elementi so razporejeni v zelo pravilnem vzorcu. Potem pa je polje stagniralo. »Freimanov prvotni dokaz je bil izredno težko razumeti, do te mere, da nihče ni bil popolnoma prepričan, da je pravilen. Tako da v resnici ni imelo takšnega vpliva, kot bi ga lahko imelo,« je dejal Timothy Gowers, matematik na Collège de France in Univerzi v Cambridgeu ter dobitnik Fieldsove medalje. "Potem pa Imre Ruzsa vdrl na sceno."

V seriji dva članki v devetdesetih je Ruzsa ponovno dokazal Freimanov izrek z elegantnim novim argumentom. Nekaj ​​let kasneje, Katalin Marton, vplivni madžarski matematik, ki je umrl leta 2019, je prilagodil vprašanje, kaj majhna vsota pomeni o strukturi prvotnega niza. Zamenjala je tipe elementov, ki so se pojavljali v množici, in tip strukture, ki bi jo morali matematiki iskati, saj je mislila, da bo to matematikom omogočilo, da izvlečejo še več informacij. Martonova domneva je povezana z dokaznimi sistemi, teorijo kodiranja in kriptografijo ter zavzema visoko mesto v aditivni kombinatoriki.

Njena domneva se zdi "res ena najbolj osnovnih stvari, ki jih nismo razumeli," je dejal Ben Green, matematik na Univerzi v Oxfordu. To je "samo nekako podkrepilo veliko stvari, ki me zanimajo."

Green je združil moči z Gowersom, Freddie Manners Kalifornijske univerze v San Diegu in Terence tao, dobitnik Fieldsove medalje na kalifornijski univerzi v Los Angelesu, da bi oblikoval tisto, kar je izraelski matematik in bloger Gil Kalai imenovan "Ekipa” matematikov. V članku so dokazali različico domneve v skupni rabi 9. novembra.

Nets Katz, matematik z Univerze Rice, ki ni bil vključen v delo, opisuje dokaz kot "čudovito preprost" - in "bolj ali manj popolnoma nenavaden."

Tao je nato začel s prizadevanjem za formalizacijo dokaza Pusto, programski jezik, ki matematikom pomaga preverjati izreke. V samo nekaj tednih je ta trud uspel. V torek zgodaj zjutraj, 5. decembra, je sporočil Tao da je Lean dokazal domnevo brez kakršnih koli "oprostite" - standardne izjave, ki se pojavi, ko računalnik ne more preveriti določenega koraka. To je najbolj odmevna uporaba tega orodja za preverjanje od leta 2021, in označuje prelomno točko v načinih, kako matematiki pišejo dokaze v izrazih, ki jih računalnik razume. Če bodo ta orodja postala dovolj enostavna za uporabo matematikov, bodo morda lahko nadomestila pogosto dolgotrajen in težaven postopek strokovnega pregleda, je dejal Gowers.

Sestavine dokaza so tlele desetletja. Gowers je svoje prve korake zasnoval v začetku leta 2000. Vendar je trajalo 20 let, da se je dokazalo, kar je Kalai imenoval "sveti gral" na tem področju.

V skupini

Da bi razumeli Martonovo domnevo, je v pomoč poznavanje koncepta skupine, matematičnega objekta, ki je sestavljen iz množice in operacije. Pomislite na cela števila - neskončno množico števil - in operacijo seštevanja. Vsakič, ko seštejete dve celi števili, dobite drugo celo število. Seštevanje upošteva tudi nekaj drugih pravil skupinskih operacij, kot je asociativnost, ki vam omogoča spreminjanje vrstnega reda operacij: 3 + (5 + 2) = (3 + 5) + 2.

Znotraj skupine lahko včasih najdete manjše množice, ki izpolnjujejo vse lastnosti skupine. Na primer, če seštejete kateri koli dve sodi števili, boste dobili drugo sodo število. Soda števila so skupina zase, zaradi česar so podskupina celih števil. Nasprotno liha števila niso podskupina. Če seštejete dve lihi števili, dobite sodo število - ni v prvotnem nizu. Toda vsa liha števila lahko dobite tako, da vsakemu sodemu številu preprosto dodate 1. Tako premaknjeno podskupino imenujemo koset. Nima vseh lastnosti podskupine, vendar na več načinov ohranja strukturo svoje podskupine. Tako kot soda števila so na primer tudi liha števila enakomerno razporejena.

Marton je domneval, da če imaš komplet, ga bomo poklicali A sestavljen iz skupinskih elementov, katerih vsota ni toliko večja od A sama, potem obstaja neka podskupina - poimenujte jo G — s posebno lastnostjo. Shift G nekajkrat, da naredite kozete, in te kozete bodo skupaj vsebovale prvotni niz A. Poleg tega je domnevala, da število cosetov ne raste veliko hitreje od velikosti skupnega niza - verjela je, da bi moralo biti povezano s polinomskim faktorjem, v nasprotju z veliko hitrejšo eksponentno rastjo.

To se morda sliši kot zelo tehnična zanimivost. A ker se nanaša na preprost preizkus — kaj se zgodi, ko v naboru dodate samo dva elementa? — za krovno strukturo podskupine je zelo pomembna za matematike in računalničarje. Ista splošna zamisel se pojavi, ko računalničarji poskušajo šifrirati sporočila, tako da lahko naenkrat dekodirate le delček sporočila. Pojavlja se tudi v verjetnostno preverljivih dokazih, obliki dokaza, ki jo lahko računalniški znanstveniki preverijo s preverjanjem le nekaj izoliranih bitov informacij. V vsakem od teh primerov delate le z nekaj točkami v strukturi - dekodirate samo nekaj bitov iz dolgega sporočila ali preverite majhen del zapletenega dokaza - in sklepate nekaj o večji strukturi na višji ravni.

"Lahko se pretvarjate, da je vse velika podmnožica skupine," je rekel Tom Sanders, nekdanji Gowersov študent, ki je zdaj Greenov sodelavec na Oxfordu, ali pa lahko, »iz obstoja številnih dodatnih naključij dobite vse, kar ste želeli. Obe perspektivi sta uporabni.«

Ruzsa leta 1999 objavil Martonovo domnevo, ki ji pripisuje vso zaslugo. "Do te domneve je prišla neodvisno od mene in Freimana in verjetno pred nami," je dejal. "Zato sem se, ko sem govoril z njo, odločil, da bom to imenoval njena domneva." Kljub temu jo matematiki zdaj imenujejo polinomska domneva Freiman-Ruzsa ali PFR.

ničle in enote

Skupine imajo, tako kot mnogi matematični objekti, veliko različnih oblik. Marton je domneval, da njena domneva velja za vse skupine. To je treba še pokazati. Novi članek to dokazuje za določeno vrsto skupine, ki kot svoje elemente vzame sezname binarnih števil, kot je (0, 1, 1, 1, 0). Ker računalniki delujejo v binarnem sistemu, je ta skupina v računalništvu ključna. Uporaben pa je bil tudi v aditivni kombinatoriki. "To je kot nekakšna nastavitev igrače, v kateri se lahko nekako igrate in poskušate stvari," je dejal Sanders. "Algebra je veliko, veliko lepša" kot delo s celimi števili, je dodal.

Seznami imajo fiksne dolžine in vsak bit je lahko 0 ali 1. Seštejete jih tako, da vsak vnos dodate njegovemu nasprotniku na drugem seznamu s pravilom, da je 1 + 1 = 0. Torej (0, 1, 1, 1 , 0) + (1, 1, 1, 1, 1) = (1, 0, 0, 0, 1). PFR je poskus ugotoviti, kako lahko izgleda niz, če ni ravno podskupina, ampak ima nekatere lastnosti, podobne skupini.

Da bi bil PFR natančen, si predstavljajte, da imate nabor klicanih binarnih seznamov A. Zdaj vzemite vsak par elementov iz A in jih seštejte. Dobljene vsote sestavljajo vsoto A, klical A + A. Če so elementi A izbrani naključno, potem se večina vsot med seboj razlikuje. Če obstajajo k elementi v A, to pomeni, da bo okoli k²/2 elementa v vsoti. Kdaj k je veliko - recimo 1,000 - k²/2 je veliko večji od k. Ampak če A je podskupina, vsak element A + A je v A, kar pomeni, da A + A je enake velikosti kot A Sam.

PFR upošteva nize, ki niso naključni, vendar tudi niso podskupine. V teh sklopih je število elementov v A + A je nekoliko majhen - recimo 10kAli 100k. "Res je uporabno, ko je vaša predstava o strukturi veliko bolj bogata kot le natančna algebraična struktura," je dejal Shachar Lovett, računalniški znanstvenik na kalifornijski univerzi v San Diegu.

Vse množice, ki so jih poznali matematiki in so upoštevale to lastnost, "so precej blizu dejanskim podskupinam," je dejal Tao. "To je bila intuicija, da naokoli ne obstajajo nobene druge vrste lažnih skupin." Freiman je v svojem izvirnem delu dokazal različico te izjave. Leta 1999 je Ruzsa razširil Freimanov izrek s celih števil na nastavitev binarnih seznamov. Dokazal je da ko je število elementov v A + A je stalni mnogokratnik velikosti A, A je v podskupini.

Toda Ruzsin izrek je zahteval, da je podskupina ogromna. Martonov vpogled je bil v predpostavki, da namesto da bi bil vsebovan v eni velikanski podskupini, A lahko vsebovan v polinomskem številu kosetov podskupine, ki ni večja od prvotne množice A.

'Poznam pravo idejo, ko vidim pravo idejo'

Na prelomu tisočletja je Gowers naletel na Ruzsine dokaze Freimanovega izreka, medtem ko je preučeval drugačen problem o množicah, ki vsebujejo nize enakomerno razporejenih števil. "Potreboval sem nekaj takega, nekakšno pridobivanje strukturnih informacij iz veliko bolj ohlapnih informacij o določenem nizu," je dejal Gowers. "Imel sem veliko srečo, da je nedolgo prej Ruzsa pripravila ta absolutno čudovit dokaz."

Gowers je začel pripravljati potencialni dokaz polinomske različice domneve. Njegova ideja je bila začeti s setom A katerih skupek je bil razmeroma majhen, nato postopoma manipulirati A v podskupino. Če bi lahko dokazal, da je nastala podskupina podobna prvotnemu nizu A, je zlahka sklepal, da je domneva resnična. Gowers je delil svoje ideje s kolegi, vendar jih nihče ni mogel oblikovati v popoln dokaz. Čeprav je bila Gowersova strategija v nekaterih primerih uspešna, so v drugih manipulacije trajale A dlje od želenega zaključka polinomske domneve Freiman-Ruzsa.

Sčasoma se je polje premaknilo naprej. Leta 2012 je Sanders skoraj dokazano PFR. Toda število premaknjenih podskupin, ki jih je potreboval, je bilo nad polinomsko ravnjo, čeprav le za malenkost. "Ko je to storil, je to pomenilo, da je to postala manj nujna stvar, a še vedno res lepa težava, ki mi je zelo všeč," je dejal Gowers.

Toda Gowersove ideje so živele naprej v spominih in na trdih diskih njegovih kolegov. "Tam je prava ideja," je dejal Green, ki je bil tudi Gowersov študent. "Pravo idejo poznam, ko vidim pravo idejo." Letos poleti so Green, Manners in Tao končno osvobodili Gowersove zamisli iz njihovega čistilišča.

Green, Tao in Manners so sodelovali 37 strani, preden so se odločili vrniti k Gowersovim 20 let starim zamislim. V 23. juniju papirja, so uspešno uporabili koncept iz teorije verjetnosti, imenovan naključne spremenljivke, da bi raziskali strukturo množic z majhnimi vsotami. S tem preklopom bi skupina lahko manipulirala s svojimi kompleti z več finosti. "Ukvarjanje z naključnimi spremenljivkami je nekako veliko manj togo kot obravnavanje množic," je dejal Manners. Z naključno spremenljivko "lahko prilagodim eno od verjetnosti za majhno količino in to mi lahko da boljšo naključno spremenljivko."

Z uporabo te verjetnostne perspektive so se Green, Manners in Tao lahko premaknili od dela s številom elementov v nizu k merjenju informacij, ki jih vsebuje naključna spremenljivka, količina, imenovana entropija. Entropija ni bila novost v aditivni kombinatoriki. Pravzaprav Tao je poskušal za popularizacijo koncepta v poznih 2000-ih. Toda nihče ga še ni poskusil uporabiti na polinomski domnevi Freiman-Ruzsa. Green, Manners in Tao so ugotovili, da je močan. A še vedno niso mogli dokazati domneve.

Ko je skupina prežvekovala svoje nove rezultate, so ugotovili, da so končno zgradili okolje, v katerem bi Gowersove speče ideje lahko uspevale. Če bi merili velikost nabora z uporabo njegove entropije in ne števila elementov, bi tehnične podrobnosti morda delovale veliko bolje. »Na neki točki smo ugotovili, da so te Timove stare zamisli izpred 20 let dejansko bolj uspešne kot tiste, ki smo jih preizkušali,« je dejal Tao. »In tako smo Tima vrnili k projektu. In potem se vsi kosi presenetljivo lepo prilegajo skupaj.”

Kljub temu je bilo treba ugotoviti veliko podrobnosti, preden se je sestavil dokaz. "Nekako neumno je bilo, da smo bili vsi štirje neverjetno zaposleni z drugimi stvarmi," je dejal Manners. "Želite objaviti ta odličen rezultat in povedati svetu, vendar morate dejansko še vedno napisati svoje vmesne izpite." Sčasoma se je skupina prebila in 9. novembra objavila svoj članek. Dokazali so, da če A + A ni večji od k krat večja od A, Potem A lahko pokrije največ približno k¹² premiki podskupine, ki ni večja od A. To je potencialno ogromno število menjav. Vendar je polinom, zato ne raste eksponentno hitreje kot k postane večja, kot bi, če k bili v eksponentu.

Nekaj ​​dni kasneje, Tao začel z formalizirati dokaz. Skupaj je vodil projekt formalizacije z uporabo paketa za nadzor različic GitHub za usklajevanje prispevkov iz 25 prostovoljcev po vsem svetu. Uporabili so orodje, imenovano Blueprint ki ga je razvil Patrick Massot, matematik na univerzi Paris-Saclay, da bi organiziral prizadevanja za prevajanje iz tega, kar je tao se imenuje »Matematična angleščina« v računalniško kodo. Blueprint lahko med drugim ustvari a grafikon prikazujejo različne logične korake, vključene v dokaz. Ko so bili vsi mehurčki pokriti s tem, kar je Tao imenoval "lep odtenek zelene", je ekipa končala. V časopisu so odkrili nekaj zelo manjših tipkarskih napak - na spletu Sporočilo, je Tao opozoril, da je bilo "matematično najbolj zanimive dele projekta razmeroma preprosto formalizirati, vendar so bili tehnični 'očitni' koraki tisti, ki so trajali najdlje."

Marton je umrla le nekaj let, preden je bila njena slavna domneva dokazana, vendar dokaz odmeva z njo življenjsko delo o entropiji in informacijski teoriji. "Vse deluje veliko bolje, če to počnete v tem entropijskem okviru kot v okviru, ki sem ga poskušal narediti," je dejal Gowers. "Meni se zdi še vedno nekoliko čarobno."

Quanta izvaja vrsto anket, da bi bolje služil svojemu občinstvu. Vzemite našo anketa bralcev matematike in vključeni boste v brezplačno zmago Quanta roba.