Lähivaade näitab lõpmatu graafiku sulamispunkti | Quanta ajakiri

2008. aastal suri matemaatik Oded Schramm matkaõnnetuses Cascade'i mägedes umbes 50 miili Seattle'ist idas. Kuigi ta oli vaid 46-aastane, oli ta loonud täiesti uued matemaatikavaldkonnad.

"Ta oli fantastiline matemaatik," ütles Itai Benjamini, Weizmanni teadusinstituudi matemaatik ning Schrammi sõber ja kaastööline. "Äärmiselt loominguline, äärmiselt elegantne, äärmiselt originaalne."

Tema esitatud küsimused nihutavad endiselt tõenäosusteooria ja statistilise füüsika piire. Paljud neist küsimustest puudutavad matemaatilisi struktuure, millel on faasiüleminek - äkiline makroskoopiline muutus, nagu jää sulamine veeks. Nii nagu erinevatel materjalidel on erinevad sulamistemperatuurid, on ka matemaatiliste struktuuride faasisiirded erinevad.

Schramm oletas, et faasisiiret protsessis, mida nimetatakse perkolatsiooniks, saab hinnata, kasutades paljude oluliste matemaatiliste struktuuride jaoks ainult süsteemi lähivaadet, mida nimetatakse kohalikuks perspektiiviks. Täielikult välja suumimine ja kogu asja vaatamine ei muuda arvutust oluliselt. Viimase 15 aasta jooksul on matemaatikud oletuse väikseid tükke ära lõiganud, kuid siiani pole nad suutnud seda täielikult lahendada.

Aastal eeltrükk postitatud oktoobris, Tom Hutchcroft California Tehnoloogiainstituudist ja tema doktorant Philip Easo tõestas Schrammi paikkonna oletust. Nende tõestus põhineb peamistel ideedel tõenäosusteooriast ja muudest matemaatika valdkondadest, mida nad nutikalt kombineerisid.

"See on tähelepanuväärne paber. See on pika töö kuhjumine, ”ütles Benjamini.

Lõpmatud klastrid

Sõna "perkolatsioon" viitas algselt vedeliku liikumisele läbi poorse keskkonna, näiteks vee, mis voolab läbi kohvipaksu või õli imbub läbi kivipragude.

1957. aastal töötasid matemaatikud Simon Ralph Broadbent ja John Michael Hammersley välja selle füüsikalise protsessi matemaatilise mudeli. Sellest ajast möödunud aastakümnete jooksul on sellest mudelist saanud omaette uurimisobjekt. Matemaatikud uurivad perkolatsiooni, kuna see saavutab olulise tasakaalu: seadistamine on lihtne, kuid sellel on keerukad ja mõistatuslikud omadused.

"See on omamoodi kanooniline mudel matemaatikute jaoks, " ütles Hutchcroft. "Sa suudad asju visuaalselt mõelda. See teeb koos töötamise tõeliselt meeldivaks. ”

Perkolatsioon algab graafiga, mis on tippude (punktide) kogum, mida saab ühendada servade (joontega). Üks lihtsamaid näiteid on ruutvõrk, mille tipud on joondatud, et moodustada ruutude nurgad ja mõnda neist ühendavad servad.

Vahetult enne oma surma oletas Schramm, et Grimmetti ja Marstrandi teoreemi saab üldistada. Ta arvas, et perkolatsiooniläve määrab suure graafikute klassi transitiivsete graafikutena tuntud lähivõte ehk "mikroskoopiline" perspektiiv.

Aastal 2009, Benjamini, Asaf Nachmias ja Yuval Peres tõestatud Schrammi paikkonna oletus, nagu see praegu on tuntud, konkreetset tüüpi transitiivse graafi kohta, mis meenutab puud. Schramm oli aga oletanud, et see kehtib kõigi transitiivsete graafikute puhul (erandiks on ühemõõtmelised graafikud).

Transitiivses graafis näevad kõik tipud välja sarnased. Kahemõõtmeline võrk on üks näide. Kui valite mis tahes kaks tippu, võite alati leida sümmeetria, mis viib ühe tipu teise.

See seos kehtib kõigi transitiivsete graafikute puhul. Nende sümmeetriate tõttu näevad need samasugused välja, kui suumite sisse ja vaatate transitiivse graafiku kahte võrdse suurusega plaastrit. Sel põhjusel arvas Schramm, et lähivaade on piisav, et võimaldada matemaatikutel arvutada kõigi transitiivsete graafikute perkolatsioonilävi.

Transitiivsetel graafikutel võib olla palju kujundeid ja vorme. Need võivad olla lihtsad ruudustikud, mis koosnevad ruutudest, kolmnurkadest, kuusnurkadest või mõnest muust kujundist. Või võivad nad moodustada keerukama objekti, näiteks "3-regulaarse puu", kus üks keskpunkt ühendub kolme tipuga ja seejärel hargneb iga tipp, et luua lõpmatuseni kaks uut, mille paar esimest sammu on näha siin:

Transitiivsete graafikute mitmekesisus aitas kaasa Schrammi paikkonna oletuse tõestamise raskustele. 15 aasta jooksul Schrammi oletuse ning Easo ja Hutchcrofti tõestuse vahel tõestasid mitmed matemaatikute rühmad oletusi teatud tüüpi graafikute kohta, kuid nende ideed ei laienenud kunagi üldisele juhtumile.

"Kõigi võimalike geomeetriate ruum on lihtsalt nii suur ja alati varitsevad veidrad asjad," ütles Hutchcroft.

Objektiivi laiendamine

Easo ja Hutchcroft ei otsinud algselt lahendust Schrammi lokaalsuse oletustele, mis kehtivad lõpmatute graafikute kohta. Selle asemel uurisid nad lõplikel graafikutel perkolatsiooni. Kuid neil oli idee, mis pööras ootamatult nende tähelepanu oletustele.

"Mõtlesime selle uue tööriistaga ja mõtlesime, et oh, see tundub olevat selline asi, mis võib paikkonna ründamisel abiks olla," ütles Easo.

Oletuse tõestamiseks pidid nad näitama, et mikroskoopiline perspektiiv annab täpse ülevaate perkolatsioonilävest. Kui vaatate ainult osa graafikust ja vaatlete suurt ühendatud klastrit, võite eeldada, et graafikul on lõpmatu klaster ja see on seega üle perkolatsiooniläve. Easo ja Hutchcroft asusid seda tõestama.

Nad tuginesid tehnikale, mida võib pidada "objektiivi laiendamiseks". Alusta ühest tipust. Seejärel suumige välja, et näha kõiki tippe, mis on algsel graafikul vaid ühe serva kaugusel. Ruutvõrgul näete nüüd kokku viit tippu. Laiendage objektiivi uuesti, et näha kõiki tippe kahe serva kaugusel ja seejärel kolme serva, nelja serva ja nii edasi kaugusel.

Easo ja Hutchcroft seadsid valikuketta, mis määrab, kui palju linke on selle lähedal, kus nad nägid suurt klastrit. Seejärel laiendasid nad objektiivi, jälgides, et nende suurde kobarasse koguneb üha rohkem servi. Seda tehes pidid nad suurendama linkide olemasolu tõenäosust, mis muudab lihtsamaks näidata, et graafikul on suur ühendatud komponent. See on delikaatne tasakaalustamine. Nad pidid laiendama vaatevälja piisavalt kiiresti ja lisama linke piisavalt aeglaselt, et paljastada täielik lõpmatu graafik ilma ketta asendit dramaatiliselt muutmata.

Nad suutsid näidata, et suured kobarad kasvavad kiiremini kui väiksemad, nii et, nagu Easo ütles, "teie kobar kasvab üha kiiremini, kui see muutub järjest suuremaks, täpselt nagu lumepalli veeretades."

Ruutvõrgu puhul kasvab tippude arv suhteliselt aeglaselt. See on ligikaudu teie objektiivi laius ruudus. 10 sammu järel leiate umbes 100 tippu. Kuid 3-haruline puu kasvab eksponentsiaalselt kiiremini – ligikaudu 2 tõstetakse teie objektiivi laiuse võrra. 10 sammu järel näete ligikaudu 1,024 tippu. Alloleval joonisel on näha, kuidas 3-regulaarne puu on juba seitsme sammu järel palju suurem, kuigi ruudustikul on alguses rohkem tippe. Üldiselt võivad graafikutel eri skaalal olla erinevad kasvumäärad – need võivad alata kiiresti ja seejärel aeglustuda.

Aastal 2018, Hutchcroft kasutas sarnast ideed et tõestada paikkonna oletust kiiresti kasvavate graafikute puhul, nagu 3-regulaarne puu. Kuid see ei töötanud aeglase kasvuga graafikute (nt ruutruudustik) või keskmise kiirusega kasvavate graafikute puhul, mis ei vasta ei kiire ega aeglase kasvu matemaatilistele kriteeriumidele.

"See on koht, kus asjad on näiteks kolm aastat tõeliselt masendavad," ütles Hutchcroft.

Struktuur versus laienemine

Erinevatel skaaladel kasvumäärasid segavate graafikute jaoks peate kasutama erinevaid tehnikaid.

Üks väga kasulik fakt on see, et nagu Easo selgitas, "kui graafik näib mingil skaalal aeglase kasvuga, siis see takerdub." Suuremates mastaapides kasvab see aeglaselt. Kuna aeglase kasvuga graafikutel on täiendav struktuur, mille määrab matemaatika haru, mida nimetatakse rühmateooriaks, oli ka teada, et kui piisavalt kaugele välja suumida, kuvatakse aeglase kasvuga graafikute geomeetria, mis on matemaatiliselt taltsas.

2021. aastal tegi Sébastien Martineau Pariisi Sorbonne'i ülikoolist koostööd Daniel Contrerase ja Vincent Tassion ETH Zürichist, sai seda vara kasutada tõestada Schrammi paikkonna oletust graafikute jaoks, mis lõpuks kasvavad aeglaselt.

Sel hetkel olid kaks matemaatikute rühma edukalt lahendanud oletused erinevatest suundadest: kiire ja aeglase kasvuga. Kuid see jättis suured lüngad. Esiteks on olemas vahepealse kasvu kategooria, mida ei hõlmanud Easo ja Hutchcrofti tehnika ega Contrerase, Martineau ja Tassioni tõend. Teine probleem oli see, et argumendid ei kehtinud ikka veel muutuva kasvumääraga graafikute puhul – ainult nende puhul, mis jäid kiireks või jäid aeglaseks. Contrerase, Martineau ja Tassioni argumendi rakendamiseks suvalistele graafikutele ei piisanud sellest, et geomeetria näib välja suumimisel lõpuks taltsas, selgitas Easo: "Meil on vaja, et see näeks praegu taltsas välja, praeguse skaala lähedal."

Eikusagi keskel

Vahepealse kasvu transitiivsed graafikud on väga salapärased. Matemaatikud pole kunagi leidnud näidet transitiivsest graafikust, mille kasv jääb sellesse vahemikku. Võimalik, et neid pole isegi olemas. Kuid matemaatikud ei ole tõestanud, et neid ei eksisteeri, nii et iga täielik tõend Schrammi paikkonna oletuse kohta peab neid käsitlema. Väljakutset suurendades pidid Easo ja Hutchcroft käsitlema graafikuid, millel võib teatud pikkusega skaalal olla vaid lühiajaline vahepealne kasv, isegi kui need kasvavad sisse või välja suumimisel kiiremini või aeglasemalt.

Easo ja Hutchcroft töötasid suure osa möödunud aastast, et laiendada oma tulemusi graafikutele, mida ükski varasem meetod ei hõlmanud.

Esiteks muutsid nad 2018. aasta tehnikat, mida Hutchcroft oli rakendanud kiiresti kasvavatele graafikutele, et töötada graafikutega, mis muudavad kasvutaset erineval skaalal. Seejärel asusid nad tegelema aeglase kasvuga juhtumiga 27-leheküljeline paber nad jagasid augustis, mis laiendas tööd Contrerase, Martineau ja Tassioniga. Lõpuks koostasid nad oma oktoobri eeltrükis veel ühe argumendi, kasutades juhuslike käimiste teooriat – jooned, mis liiguvad juhuslikult läbi ruumi –, et käsitleda vahepealset kasvu. Kui trihhotoomia oli lõpetatud, olid nad tõestanud Schrammi oletust asukohast.

"Pidime probleemile heitma kõik, mida teadsime," ütles Hutchcroft.

Lahendus annab matemaatikutele parema ülevaate sellest, mis toimub üle perkolatsiooniläve, kus lõpmatu klastri tõenäosus on 100%, ja sellest allpool, kus tõenäosus on 0%. Kuid matemaatikuid hämmastab see, mis juhtub täpselt enamiku graafikute, sealhulgas kolmemõõtmelise ruudustiku läve juures. "See on ilmselt kõige kuulsam ja kõige elementaarsem lahtine küsimus perkolatsiooniteoorias," ütles Russell Lyons Indiana ülikoolist.

Kahemõõtmeline ruudustik on üks väheseid juhtumeid, kus matemaatikud on tõestanud, mis toimub täpselt lävel: lõpmatuid klastreid ei teki. Ja pärast seda, kui Grimmett ja Marstrand tõestasid suurte plaatide asukoha oletuse versiooni, näitasid Grimmett ja kaastöötajad, et kui lõigate 3D-ruudustiku horisontaalselt pooleks, luues põranda, ja häälestate sihverplaadi täpselt perkolatsiooniläve järgi, ei teki lõpmatuid klastreid. Nende tulemus vihjab, et täielikul kolmemõõtmelisel ruudustikul, nagu ka selle kahemõõtmelisel vastel, ei pruugi perkolatsioonilävel olla lõpmatut kobarat.

1996. aastal Benjamini ja Schramm oletatud et võimalus leida lõpmatu klaster otse läve juures on kõigi transitiivsete graafikute puhul null – täpselt nagu 2D-ruudustiku või pooleks lõigatud 3D-ruudustiku puhul. Nüüd, kui paikkonna oletus on lahendatud, võib arusaam sellest, mis toimub just üleminekuhetkel, olla veidi lähemal.

Parandus: Detsember 18, 2023
Sõlmede arv lähtesõlme n lingis 3-regulaarsel graafikul kasvab ligikaudu 2ⁿ, mitte 3ⁿ nagu see artikkel algselt väitis. Artiklit on parandatud.

Quanta viib läbi mitmeid küsitlusi, et meie vaatajaskonda paremini teenindada. Võtke meie matemaatika lugejaküsitlus ja teid osaletakse tasuta võitmiseks Quanta kaup.