O vedere de aproape dezvăluie punctul de „topire” al unui grafic infinit | Revista Quanta

În 2008, matematicianul Oded Schramm a murit într-un accident de drumeție în munții Cascade, la aproximativ 50 de mile est de Seattle. Deși avea doar 46 de ani, el a construit domenii complet noi de matematică.

„A fost un matematician fantastic”, a spus Itai Benjamini, matematician la Institutul de Științe Weizmann și prieten și colaborator al lui Schramm. „Extrem de creativ, extrem de elegant, extrem de original.”

Întrebările pe care le-a pus încă împing frontierele teoriei probabilităților și ale fizicii statistice. Multe dintre aceste întrebări se referă la structurile matematice care au o tranziție de fază - o schimbare macroscopică bruscă, cum ar fi topirea gheții în apă. La fel cum diferitele materiale au puncte de topire diferite, tranzițiile de fază ale structurilor matematice variază și ele.

Schramm a presupus că tranziția de fază într-un proces numit percolare poate fi estimată folosind doar o vedere de aproape a sistemului - numită perspectiva locală - pentru multe structuri matematice importante. Mișcarea completă și privirea întregului lucru nu vor schimba în mod semnificativ calculul. În ultimii 15 ani, matematicienii au tăiat mici bucăți din conjectura, dar până acum nu au reușit să o rezolve complet.

Într-o preprint postat în octombrie, Tom Hutchcroft al Institutului de Tehnologie din California și al doctorandului său Philip Easo a dovedit conjectura localității lui Schramm. Dovada lor se bazează pe idei majore din teoria probabilității și din alte domenii ale matematicii, pe care le-au combinat într-un mod inteligent.

„Este o lucrare remarcabilă. Este o acumulare de muncă îndelungată”, a spus Benjamini.

Clustere infinite

Cuvântul „percolare” se referea inițial la mișcarea fluidului printr-un mediu poros, cum ar fi apa care curge prin zațul de cafea sau uleiul care se scurge prin crăpăturile unei stânci.

În 1957, matematicienii Simon Ralph Broadbent și John Michael Hammersley au dezvoltat un model matematic al acestui proces fizic. În deceniile de după, acest model a devenit un obiect de studiu în sine. Matematicienii studiază percolația deoarece atinge un echilibru important: configurația este simplă, dar prezintă caracteristici complexe și enigme.

„Este un fel de model canonic pentru matematicieni”, a spus Hutchcroft. „Poți să te gândești la lucruri vizual. Asta face să lucrezi cu adevărat într-adevăr.”

Percolarea începe cu un grafic, care este o colecție de vârfuri (puncte) care pot fi conectate prin muchii (linii). Unul dintre cele mai simple exemple este o grilă pătrată, cu vârfuri aliniate pentru a forma colțurile pătratelor și marginile care leagă unele dintre ele.

Cu puțin timp înainte de moartea sa, Schramm a presupus că teorema lui Grimmett și Marstrand ar putea fi generalizată. El a crezut că pragul de percolare este determinat în întregime de perspectiva de aproape, sau „microscopică”, pentru o clasă mare de grafice cunoscute sub numele de grafice tranzitive.

În 2009, Benjamini, Asaf Nachmias și Yuval Peres s-au dovedit Conjectura localității lui Schramm, așa cum este cunoscută acum, pentru un anumit tip de grafic tranzitiv care seamănă cu un copac. Schramm, cu toate acestea, postulase că ar fi valabil pentru toate graficele tranzitive (cu o excepție pentru graficele unidimensionale).

Într-un grafic tranzitiv, toate nodurile arată similar. O grilă bidimensională este un exemplu. Dacă alegeți oricare două vârfuri, puteți găsi întotdeauna o simetrie care mută un vârf la celălalt.

Această relație este valabilă pentru orice grafic tranzitiv. Din cauza acestor simetrii, dacă măriți și vă uitați la oricare două petice de dimensiuni egale ale unui grafic tranzitiv, acestea vor arăta la fel. Din acest motiv, Schramm a crezut că perspectiva de aproape era suficientă pentru a permite matematicienilor să calculeze pragul de percolare pentru toate graficele tranzitive.

Graficele tranzitive pot lua multe forme și forme. Ele pot fi o grilă simplă, formată din pătrate, triunghiuri, hexagoane sau altă formă. Sau pot forma un obiect mai complex, cum ar fi un „arboresc cu trei obișnuiți”, în care un punct central se conectează la trei vârfuri, iar fiecare vârf se ramifică apoi pentru a crea două noi la infinit, primii pași ai cărora sunt văzute aici:

Varietatea graficelor tranzitive a contribuit la dificultatea de a demonstra conjectura localității lui Schramm. În cei 15 ani dintre conjectura lui Schramm și demonstrația lui Easo și Hutchcroft, diferite grupuri de matematicieni au demonstrat presupunerea pentru anumite tipuri de grafice, dar ideile lor nu s-au extins niciodată la cazul general.

„Spațiul tuturor geometriilor posibile este atât de vast și întotdeauna sunt lucruri ciudate care pândesc”, a spus Hutchcroft.

Lărgirea lentilei

Easo și Hutchcroft nu căutau inițial o soluție pentru conjectura localității lui Schramm, care se aplică graficelor infinite. În schimb, studiau percolarea pe grafice finite. Dar au avut o idee care le-a mutat brusc atenția asupra conjecturii.

„Am venit cu acest nou instrument și ne-am gândit, oh, acesta pare genul de lucru care ar putea fi util pentru a ataca localitatea”, a spus Easo.

Pentru a demonstra conjectura, ei trebuiau să arate că perspectiva microscopică oferă o imagine exactă a pragului de percolare. Când vizualizați doar o parte a unui grafic și observați un cluster mare conectat, ați putea presupune că graficul are un cluster infinit și, prin urmare, este peste pragul de percolare. Easo și Hutchcroft și-au propus să demonstreze asta.

S-au bazat pe o tehnică care poate fi considerată „lărgirea lentilei”. Începeți de la un singur vârf. Apoi micșorați pentru a vizualiza toate vârfurile care sunt la doar o margine distanță pe graficul original. Pe grila pătrată, acum veți putea vedea cinci vârfuri în total. Lărgiți din nou lentila pentru a vedea toate vârfurile pe o distanță de două margini, apoi o distanță de trei margini, patru margini și așa mai departe.

Easo și Hutchcroft au stabilit cadranul care determină câte legături sunt aproape de locul în care au văzut un grup mare. Apoi au lărgit lentila, urmărind din ce în ce mai multe margini adunate în grupul lor mare. Pe măsură ce făceau acest lucru, au trebuit să crească probabilitatea ca legăturile să fie prezente, ceea ce face mai ușor să se arate că graficul are o componentă mare conectată. Acesta este un act de echilibru delicat. Aveau nevoie să lărgească câmpul vizual suficient de rapid și să adauge legături suficient de lent pentru a dezvălui întregul grafic infinit fără a schimba dramatic poziția cadranului.

Ei au reușit să arate că grupurile mari cresc mai repede decât cele mai mici, astfel că, așa cum a spus Easo, „clusterul tău crește din ce în ce mai repede pe măsură ce devine din ce în ce mai mare, la fel ca atunci când arunci un bulgăre de zăpadă”.

Pentru grila pătrată, numărul de vârfuri crește relativ lent. Este aproximativ lățimea lentilei dvs. la pătrat. După 10 pași, veți găsi aproximativ 100 de vârfuri. Dar un copac obișnuit de 3 crește exponențial mai repede - aproximativ 2 ridicat la puterea lățimii lentilei tale. După 10 pași, veți vedea aproximativ 1,024 de vârfuri. Ilustrația de mai jos arată cum arborele cu trei obișnuiți este mult mai mare după doar șapte pași, chiar dacă grila pătrată are mai multe vârfuri la început. În general, graficele pot avea rate de creștere diferite la scari diferite - pot începe rapid și apoi încetinesc.

În 2018, Hutchcroft a folosit o idee similară pentru a demonstra conjectura localității pentru grafice cu creștere rapidă precum arborele 3-regulat. Dar nu a funcționat pentru graficele cu creștere lentă, cum ar fi grila pătrată, sau pentru graficele care cresc cu viteză intermediară, ne îndeplinind nici criteriile matematice pentru creștere rapidă, nici pe cele pentru creștere lentă.

„Acesta este locul în care lucrurile devin cu adevărat frustrante timp de aproximativ trei ani”, a spus Hutchcroft.

Structură versus extindere

Pentru graficele care combină rate de creștere la scări diferite, trebuie să utilizați o varietate de tehnici.

Un fapt foarte util este că, după cum a explicat Easo, „dacă un grafic pare cu o creștere lentă la o anumită scară, atunci se blochează”. Va continua să crească încet la scari mai mari. Deoarece graficele cu creștere lentă au o structură suplimentară determinată de o ramură a matematicii numită teoria grupurilor, se știa și că, dacă micșorați suficient de mult, graficele cu creștere lentă afișează o geometrie care este blândă din punct de vedere matematic.

În 2021, Sébastien Martineau de la Universitatea Sorbona din Paris, lucrând cu Daniel Contreras și Vincent Tassion de ETH Zurich, a putut folosi această proprietate pentru demonstrați conjectura localității lui Schramm pentru grafice care în cele din urmă cresc încet.

În acest moment, cele două grupuri de matematicieni abordaseră cu succes conjectura din direcții diferite: creștere rapidă și creștere lentă. Dar acest lucru a lăsat lacune considerabile. În primul rând, există o categorie de creștere intermediară care nu a fost acoperită de tehnica lui Easo și Hutchcroft sau de demonstrația lui Contreras, Martineau și Tassion. O altă problemă a fost că argumentele încă nu s-au aplicat graficelor cu rate de creștere în schimbare - doar cele care au rămas rapide sau lente. Pentru ca argumentul Contreras, Martineau și Tassion să fie aplicat graficelor arbitrare, nu a fost suficient ca geometria să pară în cele din urmă îmblânzită atunci când micșorați, a explicat Easo: „Avem nevoie să pară blând acum, aproape de scara actuală”.

Mijlocul Nicăieri

Graficele tranzitive ale creșterii intermediare sunt foarte misterioase. Matematicienii nu au găsit niciodată un exemplu de grafic tranzitiv a cărui creștere se încadrează în acest interval. Este posibil să nu existe nici măcar. Dar matematicienii nu au dovedit că nu există, așa că orice dovadă completă a conjecturii de localitate a lui Schramm trebuie să le abordeze. Adăugând provocării, Easo și Hutchcroft trebuiau să abordeze graficele care ar putea avea doar pentru scurt timp o creștere intermediară la o anumită scară de lungime, chiar dacă cresc mai repede sau mai lent când măriți sau micșorați.

Easo și Hutchcroft au petrecut o mare parte din ultimul an lucrând pentru a-și extinde rezultatele pentru a se aplica graficelor care nu au fost acoperite de niciuna dintre metodele anterioare.

În primul rând, au modificat tehnica din 2018 pe care Hutchcroft o aplicase graficelor cu creștere rapidă pentru a lucra pe grafice care modifică nivelurile de creștere la diferite scale. Apoi au abordat cazul cu creștere lentă, în o lucrare de 27 de pagini au împărtășit în august că a extins lucrările despre Contreras, Martineau și Tassion. În cele din urmă, în preprintul lor din octombrie, ei au conceput un alt argument folosind teoria mersurilor aleatorii - linii care se mișcă aleatoriu prin spațiu - pentru a gestiona cazul cu creștere intermediară. Odată cu tricotomia finalizată, ei au dovedit conjectura localității lui Schramm.

„A trebuit să aruncăm tot ce știam la problemă”, a spus Hutchcroft.

Soluția le oferă matematicienilor o perspectivă mai bună asupra a ceea ce se întâmplă peste pragul de percolare, unde șansa unui cluster infinit este de 100% și sub acesta, unde șansa este de 0%. Dar matematicienii sunt încă nedumeriți de ceea ce se întâmplă exact la pragul pentru majoritatea graficelor, inclusiv grila tridimensională. „Aceasta este probabil cea mai faimoasă și cea mai elementară întrebare deschisă din teoria percolației”, a spus Russell Lyons de la Universitatea Indiana.

Grila bidimensională este unul dintre puținele cazuri în care matematicienii au demonstrat ce se întâmplă exact la prag: clustere infinite nu se formează. Și după ce Grimmett și Marstrand au demonstrat o versiune a conjecturii de localitate pentru plăci mari, Grimmett și colaboratorii au arătat că dacă tăiați o grilă 3D în jumătate pe orizontală, creând o podea și reglați cadranul exact la pragul de percolare, nu apar clustere infinite. Rezultatul lor sugerează că grila completă tridimensională, ca și omologul său bidimensional, ar putea să nu aibă un cluster infinit la pragul de percolare.

În 1996, Benjamini și Schramm conjecturat că șansa de a găsi un cluster infinit chiar la prag este zero pentru toate graficele tranzitive — la fel cum este pentru grila 2D sau pentru grila 3D tăiată în jumătate. Acum că conjectura localității a fost stabilită, înțelegerea a ceea ce se întâmplă chiar în punctul de tranziție ar putea fi puțin mai aproape.

Corecţie: December 18, 2023
Numărul de noduri din n legături ale unui nod de pornire pe un grafic cu 3 obișnuit crește cu aproximativ 2ⁿ, nu 3ⁿ așa cum a afirmat inițial acest articol. Articolul a fost corectat.

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.