„A-Team” de matematică dovedește o legătură critică între adunare și seturi | Revista Quanta

Într-un set de numere alese aleatoriu, adunarea poate deveni sălbatică.

Adunați fiecare pereche dintr-un astfel de set și veți ajunge cu o nouă listă care probabil va avea mult mai multe numere decât cele cu care ați început. Începeți cu 10 numere aleatoare, iar această nouă listă (numită sumset) va avea aproximativ 50 de elemente. Începeți cu 100 și sumset-ul va avea probabil în jur de 5,000; 1,000 de numere inițiale aleatoare vor face o sumă lungă de 500,000 de numere.

Dar dacă setul tău inițial are structură, suma poate ajunge cu mai puține numere decât aceasta. Luați în considerare un alt set de 10 numere: toate numerele pare de la 2 la 20. Deoarece perechi diferite se vor aduna la același număr - 10 + 12 este același cu 8 + 14 și 6 + 16 - suma are doar 19 numere, nu 50. Această diferență devine din ce în ce mai profundă pe măsură ce seturile devin mai mari. O listă structurată de 1,000 de numere ar putea avea o sumă cu doar 2,000 de numere în ea.

În anii 1960, un matematician a numit Gregory Freiman a început să investigheze mulțimi cu sume mici, într-un efort de a investiga legătura dintre adăugare și structura seturilor - o conexiune crucială care definește domeniul matematic al combinatoriei aditive. Freiman a făcut progrese impresionante, demonstrând că un set cu o sumă mică trebuie să fie conținut de un set mai mare ale cărui elemente sunt distanțate într-un model foarte regulat. Dar apoi câmpul a stagnat. „Dovada originală a lui Freiman a fost extraordinar de greu de înțeles, până la punctul în care nimeni nu era absolut sigur că este corectă. Deci nu a avut impactul pe care l-ar fi putut avea”, a spus Timothy Gowers, matematician la Collège de France și la Universitatea din Cambridge și medaliat Fields. "Dar apoi Imre Ruzsa a izbucnit în scenă.”

Într-o serie de Două lucrări în anii 1990, Ruzsa a demonstrat din nou teorema lui Freiman cu un nou argument elegant. Cativa ani mai tarziu, Catherine Marton, un matematician maghiar influent care a murit în 2019, a modificat întrebarea ce implică un mic sumset despre structura setului original. Ea a înlocuit tipurile de elemente care au apărut în set și tipul de structură pe care matematicienii ar trebui să o caute, gândindu-se că le-ar permite matematicienilor să extragă și mai multe informații. Conjectura lui Marton are legături cu sistemele de demonstrare, teoria codificării și criptografie și ocupă un loc înalt în combinatoria aditivă.

Conjectura ei „pare într-adevăr unul dintre cele mai elementare lucruri pe care nu le-am înțeles”, a spus Ben Green, un matematician la Universitatea din Oxford. „Doar că a stat la baza o mulțime de lucruri la care îmi pasă”.

Green și-a unit forțele cu Gowers, Freddie Manners de la Universitatea din California, San Diego, și Terence tao, medaliat Fields la Universitatea din California, Los Angeles, pentru a forma ceea ce matematicianul și bloggerul israelian Gil Kalai numită „O echipă” a matematicienilor. Au demonstrat o versiune a conjecturii într-o lucrare împărtășit pe 9 noiembrie.

Nets Katz, un matematician de la Universitatea Rice care nu a fost implicat în lucrare, descrie demonstrația ca fiind „foarte de simplă” și „mai mult sau mai puțin din senin”.

Tao a început apoi un efort de a oficializa dovada sarac, un limbaj de programare care îi ajută pe matematicieni să verifice teoremele. În doar câteva săptămâni, acel efort a reușit. Marți devreme dimineața zilei de 5 decembrie, anunță Tao că Lean a dovedit conjectura fără niciun „scuze” – afirmația standard care apare atunci când computerul nu poate verifica un anumit pas. Aceasta este cea mai populară utilizare a acestora instrumente de verificare din 2021, și marchează un punct de inflexiune în modul în care matematicienii scriu dovezi în termeni pe care un computer poate înțelege. Dacă aceste instrumente devin suficient de ușor de utilizat pentru matematicieni, ele ar putea fi capabile să înlocuiască procesul adesea prelungit și oneros de evaluare inter pares, a spus Gowers.

Ingredientele dovezii fierbeau de zeci de ani. Gowers și-a conceput primii pași la începutul anilor 2000. Dar a fost nevoie de 20 de ani pentru a demonstra ceea ce Kalai a numit „un Sfânt Graal” al câmpului.

În grup

Pentru a înțelege conjectura lui Marton, ajută să fii familiarizat cu conceptul de grup, un obiect matematic care constă dintr-o mulțime și o operație. Gândiți-vă la numere întregi — un set infinit de numere — și la operația de adunare. De fiecare dată când adăugați două numere întregi, obțineți un alt număr întreg. Adunarea respectă și alte câteva reguli ale operațiilor de grup, cum ar fi asociativitatea, care vă permite să schimbați ordinea operațiilor: 3 + (5 + 2) = (3 + 5) + 2.

În cadrul unui grup, uneori puteți găsi seturi mai mici care satisfac toate proprietățile grupului. De exemplu, dacă adăugați oricare două numere pare, veți obține un alt număr par. Numerele pare sunt un grup în sine, făcându-le un subgrup de numere întregi. Numerele impare, prin contrast, nu sunt un subgrup. Dacă adunați două numere impare, obțineți un număr par - nu în setul original. Dar puteți obține toate numerele impare adăugând pur și simplu 1 la fiecare număr par. Un subgrup deplasat ca acesta se numește claset. Nu are toate proprietățile unui subgrup, dar păstrează structura subgrupului său în multe feluri. De exemplu, la fel ca numerele pare, numerele impare sunt toate spațiate uniform.

Marton a presupus că, dacă ai un set, îl vom suna A alcătuit din elemente de grup a căror sumă nu este cu mult mai mare decât A în sine, atunci există un subgrup - numiți-o G — cu o proprietate specială. Schimb G de câteva ori pentru a face sectoare, iar acele seturi, luate împreună, vor conține setul original A. Mai mult, ea a presupus că numărul de seturi nu crește mult mai repede decât dimensiunea sumsetului - ea credea că ar trebui să fie legat de un factor polinomial, spre deosebire de creșterea exponențială mult mai rapidă.

Aceasta ar putea suna ca o curiozitate extrem de tehnică. Dar pentru că se referă la un test simplu - ce se întâmplă când adăugați doar două elemente în set? — pentru structura generală a unui subgrup, este foarte important pentru matematicieni și informaticieni. Aceeași idee generală apare atunci când informaticienii încearcă să cripteze mesajele, astfel încât să puteți decoda doar o parte din mesaj la timp. Apare, de asemenea, în dovezi verificabile probabil, o formă de dovadă pe care informaticienii o pot verifica verificând doar câteva fragmente izolate de informații. În fiecare dintre aceste cazuri, lucrezi doar cu câteva puncte dintr-o structură - decodând doar câțiva biți dintr-un mesaj lung sau verificând o mică parte dintr-o dovadă complicată - și concluzi ceva despre o structură mai mare, de nivel superior.

„Puteți fie să pretindeți că totul este un subset mare al unui grup”, a spus Tom Sanders, un fost student al lui Gowers care este acum coleg cu Green’s la Oxford, sau poți „obține tot ce ți-ai dorit din existența multor coincidențe aditive. Ambele perspective sunt utile.”

Ruza a publicat conjectura lui Marton în 1999, acordându-i întregul credit. „Ea a ajuns la această presupunere independent de mine și de Freiman și, probabil, înaintea noastră”, a spus el. „De aceea, când am vorbit cu ea, am decis să o numesc presupunerea ei.” Cu toate acestea, matematicienii se referă acum la ea ca polinomul conjectura Freiman-Ruzsa sau PFR.

Zerouri și Unuri

Grupurile, ca multe obiecte matematice, iau o mulțime de forme diferite. Marton a presupus că presupunerea ei este adevărată pentru toate grupurile. Acest lucru nu a fost încă arătat. Noua lucrare demonstrează acest lucru pentru un anumit tip de grup, care ia ca elemente liste de numere binare precum (0, 1, 1, 1, 0). Deoarece computerele funcționează în binar, acest grup este crucial în informatică. Dar a fost util și în combinatorie aditivă. „Este ca acest decor de jucărie în care poți să te joci și să încerci lucruri”, a spus Sanders. „Algebra este mult, mult mai plăcută” decât lucrul cu numere întregi, a adăugat el.

Listele au lungimi fixe și fiecare bit poate fi fie 0, fie 1. Le adunați împreună adăugând fiecare intrare la omologul său dintr-o altă listă, cu regula că 1 + 1 = 0. Deci (0, 1, 1, 1 , 0) + (1, 1, 1, 1, 1) = (1, 0, 0, 0, 1). PFR este o încercare de a afla cum poate arăta un set dacă nu este chiar un subgrup, dar are unele caracteristici asemănătoare grupului.

Pentru a face PFR precis, imaginați-vă că aveți un set de liste binare numite A. Acum ia fiecare pereche de elemente din A și adună-le. Sumele rezultate alcătuiesc suma de A, Numit A + A. Dacă elementele de A sunt alese aleatoriu, atunci majoritatea sumelor sunt diferite unele de altele. Dacă există k elemente în A, asta înseamnă că vor fi în jur k²/2 elemente în sumset. Când k este mare - să zicem, 1,000 - k²/2 este mult mai mare decât k. Dar dacă A este un subgrup, fiecare element al A + A este in A, ceea ce înseamnă că A + A are aceeași dimensiune ca A însăși.

PFR ia în considerare mulțimi care nu sunt aleatoare, dar nu sunt nici subgrupuri. În aceste seturi, numărul de elemente în A + A este oarecum mic - să zicem, 10k, Sau 100k. „Este cu adevărat util atunci când noțiunea ta de structură este mult mai bogată decât a fi doar o structură algebrică exactă”, a spus Shachar Lovett, un informatician la Universitatea din California, San Diego.

Toate seturile pe care matematicienii le știau și care respectă această proprietate „sunt destul de aproape de subgrupurile reale”, a spus Tao. „Aceasta a fost intuiția, că nu existau niciun alt fel de grupuri false.” Freiman dovedise o versiune a acestei afirmații în lucrarea sa originală. În 1999, Ruzsa a extins teorema lui Freiman de la numere întregi la setarea listelor binare. El a dovedit că atunci când numărul de elemente în A + A este un multiplu constant al mărimii lui A, A este cuprinsă într-un subgrup.

Dar teorema lui Ruzsa cere ca subgrupul să fie enorm. Perspectiva lui Marton a fost să postuleze că, în loc să fie cuprins într-un subgrup uriaș, A ar putea fi conținut într-un număr polinom de clase ale unui subgrup care nu este mai mare decât mulțimea inițială A.

„Cunosc o idee reală când văd o idee reală”

La începutul mileniului, Gowers a dat peste dovezile lui Ruzsa ale teoremei lui Freiman în timp ce studia o problemă diferită despre mulțimile care conțin șiruri de numere uniform distanțate. „Aveam nevoie de așa ceva, să obțin informații structurale din informații mult mai laxe despre un anumit set”, a spus Gowers. „Am fost foarte norocos că nu cu mult timp înainte, Ruzsa a produs această dovadă absolut superbă.”

Gowers a început să elaboreze o dovadă potențială a versiunii polinomiale a conjecturii. Ideea lui a fost să înceapă cu un set A al căror sumset era relativ mic, apoi manipulați treptat A într-un subgrup. Dacă ar putea dovedi că subgrupul rezultat este similar cu setul original A, a putut concluziona cu ușurință că presupunerea este adevărată. Gowers le-a împărtășit ideile colegilor, dar nimeni nu le-a putut transforma într-o dovadă completă. Deși strategia lui Gowers a avut succes în unele cazuri, în altele manipularea a durat A mai departe de concluzia dorită a conjecturii polinomului Freiman-Ruzsa.

În cele din urmă, câmpul s-a mutat mai departe. În 2012, Sanders aproape dovedit PFR. Dar numărul de subgrupuri deplasate de care avea nevoie era peste nivelul polinomului, deși doar puțin. „Odată ce a făcut asta, a însemnat că a devenit un lucru mai puțin urgent, dar totuși o problemă foarte frumoasă pentru care am o mare pasiune”, a spus Gowers.

Dar ideile lui Gowers au trăit în amintirile și hard disk-urile colegilor săi. „Există o idee reală acolo”, a spus Green, care fusese și student la Gowers. „Cunosc o idee reală când văd o idee reală.” În această vară, Green, Manners și Tao au eliberat în sfârșit ideile lui Gowers din purgatoriul lor.

Green, Tao și Manners au avut 37 de pagini în colaborare înainte de a se gândi să revină la ideile vechi de 20 de ani ale lui Gowers. Într-un 23 iunie hârtie, au folosit cu succes un concept din teoria probabilității numit variabile aleatoare pentru a sonda structura mulțimilor cu sume mici. Făcând această schimbare, grupul și-ar putea manipula seturile cu mai multă finețe. „Confruntarea cu variabile aleatoare este oarecum mult mai puțin rigidă decât a se ocupa de seturi”, a spus Manners. Cu o variabilă aleatorie, „Pot ajusta una dintre probabilități cu o sumă mică, iar asta mi-ar putea oferi o variabilă aleatoare mai bună.”

Folosind această perspectivă probabilistică, Green, Manners și Tao ar putea trece de la lucrul cu numărul de elemente dintr-un set la o măsurare a informațiilor conținute într-o variabilă aleatorie, o cantitate numită entropie. Entropia nu era nouă în combinatoria aditivă. De fapt, Tao încercase pentru a populariza conceptul la sfârșitul anilor 2000. Dar nimeni nu încercase încă să-l folosească pe conjectura polinomul Freiman-Ruzsa. Green, Manners și Tao au descoperit că este puternic. Dar ei încă nu au putut dovedi presupunerea.

În timp ce grupul își mesteca noile rezultate, și-au dat seama că în sfârșit au construit un mediu în care ideile latente ale lui Gowers ar putea înflori. Dacă ar măsura dimensiunea unui set folosind entropia sa, mai degrabă decât numărul de elemente, detaliile tehnice ar putea funcționa mult mai bine. „La un moment dat, ne-am dat seama că aceste idei vechi de la Tim de acum 20 de ani aveau de fapt mai multe șanse să funcționeze decât cele pe care le încercam”, a spus Tao. „Și așa l-am adus pe Tim înapoi în proiect. Și apoi toate piesele se potrivesc surprinzător de frumos.”

Cu toate acestea, au fost multe detalii de aflat înainte de a se aduna o dovadă. „A fost o prostie că toți patru am fost incredibil de ocupați cu alte lucruri”, a spus Manners. „Vrei să publicați acest rezultat grozav și să spuneți lumii, dar de fapt, trebuie să vă scrieți examenul intermediar.” În cele din urmă, grupul a trecut, iar pe 9 noiembrie și-au postat ziarul. Au demonstrat că dacă A + A nu este mai mare decât k ori mai mare de A, Apoi A poate fi acoperit cu nu mai mult de aproximativ k¹² schimbări ale unui subgrup care nu este mai mare decât A. Acesta este un număr potențial enorm de schimburi. Dar este un polinom, așa că nu crește exponențial mai repede ca k devine mai mare, așa cum ar fi k erau în exponent.

Câteva zile mai târziu, Tao A inceput sa oficializează dovada. A condus proiectul de formalizare în colaborare, folosind pachetul de control al versiunii GitHub pentru a coordona contribuțiile de la 25 de voluntari din întreaga lume. Au folosit un instrument numit Blueprint dezvoltat de Patrick Massot, matematician la Universitatea Paris-Saclay, pentru a organiza eforturile de a traduce din ceea ce Tao denumit „Engleză matematică” în codul computerului. Blueprint poate, printre altele, să creeze un diagramă înfățișând diferiții pași logici implicați în demonstrație. Odată ce toate bulele au fost acoperite cu ceea ce Tao a numit o „nuanță minunată de verde”, echipa a terminat. Ei au descoperit câteva greșeli foarte minore în ziare - într-un online mesaj, Tao a remarcat că „porțiunile cele mai interesante din punct de vedere matematic ale proiectului au fost relativ ușor de oficializat, dar pașii tehnici „evidenți” au fost cei care au durat cel mai mult.”

Marton a murit cu doar câțiva ani înainte ca faimoasa ei presupunere să fie dovedită, dar dovada îi răsună munca vieții despre entropie și teoria informației. „Totul funcționează mult mai bine atunci când o faci în acest cadru de entropie decât în ​​cadrul pe care încercam să o fac”, a spus Gowers. „Mie, încă mi se pare oarecum magic.”

Cuante efectuează o serie de sondaje pentru a servi mai bine publicul nostru. Ia-ne sondaj pentru cititorii de matematică și vei fi înscris pentru a câștiga gratuit Cuante Merch.