Tõenäosuse ja arvuteooria põrkumine – hetkega

Nende ambitsioonid olid alati kõrged. Kui Will Sawin ja Melanie Matchett Wood 2020. aasta suvel esimest korda koos koostööd alustasid, otsustasid nad arvuteooria kõige ahvatlevamate oletuste põhikomponendid ümber mõelda. Nende tähelepanu objektid, klassirühmad, on tihedalt seotud põhiküsimustega, kuidas aritmeetika töötab, kui numbreid laiendatakse täisarvudest kaugemale. Sawin, Columbia ülikoolis ja Wood, Harvardis, soovis teha ennustusi struktuuride kohta, mis on klassirühmast veelgi üldisemad ja matemaatiliselt hirmutavamad.

Veel enne, kui nad oma ennustuste sõnastamise lõpetasid, tõestasid nad oktoobris a uus tulemus mis võimaldab matemaatikutel rakendada üht kõige kasulikumat tõenäosusteooria tööriista mitte ainult klassirühmade, vaid ka arvude, võrkude ja paljude muude matemaatiliste objektide puhul.

"See on lihtsalt aluspaber, mille poole kõik pöörduvad, kui hakkavad nendele probleemidele mõtlema," ütles David Zureick-Brown, Emory ülikooli matemaatik. "Enam ei tundu, et peate asju nullist välja mõtlema."

Klassiseadus

Klassirühm on näide struktureeritud matemaatilisest komplektist, mida nimetatakse rühmaks. Rühmad sisaldavad palju tuttavaid komplekte, nagu täisarvud. Täisarvud teeb rühmaks, mitte lihtsalt arvude komplektiks, kuna saate selle elemendid kokku liita ja saada teise täisarvu. Üldiselt on komplekt rühm, kui sellega kaasneb mõni tehing, mis sarnaselt liitmisega ühendab kaks elementi kolmandaks elemendiks viisil, mis vastab teatud põhinõuetele. Näiteks peaks olema nulli versioon, element, mis ei muuda ühtegi teist.

Täisarvud, mida matemaatikud tavaliselt nimetavad $latex mathbb{Z}$, on lõpmatud. Kuid paljudel rühmadel on piiratud arv elemente. Näiteks nelja elemendiga rühma loomiseks kaaluge hulka {0, 1, 2, 3}. Tavalise liitmise asemel jagage suvalise kahe arvu summa 4-ga ja võtke ülejääk. (Nende reeglite kohaselt on 2 + 2 = 0 ja 2 + 3 = 1.) Seda rühma nimetatakse $latex mathbb{Z}/4mathbb{Z}$.

Üldiselt, kui soovite luua rühma $latex n$ elementidega, võite numbrid nullist läbi viia n – 1 ja arvesta ülejäänud arvuga jagamisel n. Saadud rühma nimi on $latex mathbb{Z}/nmathbb{Z}$, kuigi see pole alati ainus n elemente.

Klassirühm ilmub siis, kui arvuteoreetikud uurivad täisarvudest kaugemate arvude struktuuri. Selleks lisavad nad täisarvudele uusi numbreid, nt i (-1 ruutjuur), $latex sqrt{5}$ või isegi $latex sqrt{–5}$.

„Asjad, millega oleme numbrite puhul harjunud, ei vasta selles kontekstis enam tõele. Või vähemalt pole need tingimata tõesed, ”ütles Jordan Ellenberg, matemaatik Wisconsini ülikoolist Madisonis.

Täpsemalt, faktooring töötab täisarvude laiendites erinevalt. Kui jääte ainult täisarvude juurde, saab numbreid algarvudeks (arvudeks, mida saab jagada ainult iseenda ja 1-ga) arvesse võtta ainult ühel viisil. Näiteks 6 on 2 × 3 ja seda ei saa arvesse võtta teistes algarvudes. Seda omadust nimetatakse ainulaadseks faktoriseerimiseks.

Kuid kui lisate oma numbrisüsteemi $latex sqrt{–5}$, pole teil enam ainulaadset faktoriseerimist. Saate algarvudeks arvestada kahel erineval viisil 6. See on endiselt 2 × 3, kuid see on ka $lateks (1 + sqrt{–5}) $ × $lateks (1 – sqrt{–5}) $.

Sellistest täisarvude laienditest luuakse klassirühmad. "Klassirühmad on uskumatult olulised, " ütles Wood. "Ja seega on loomulik küsida: millised nad tavaliselt on?"

Täisarvude mis tahes laiendiga seotud klassirühma suurus on baromeeter selle kohta, kui palju kordumatut faktoriseerimist laguneb. Kuigi matemaatikud on tõestanud, et klassirühmad on alati piiratud, on nende struktuuri ja suuruse väljaselgitamine keeruline. Sellepärast 1984. aastal Henri Cohen ja Hendrik Lenstra tegi mõningaid oletusi. Nende oletused, mida nüüd nimetatakse Cohen-Lenstra heuristikaks, puudutasid kõiki klassirühmi, mis avanevad, kui lisate täisarvudele uued ruutjuured. Kui kõik need klassirühmad koondati, soovitasid Cohen ja Lenstra vastuseid küsimustele, nagu: kui suur osa neist sisaldab rühma $latex mathbb{Z}/3mathbb{Z}$? Või $latex mathbb{Z}/7mathbb{Z}$? Või mõni muu teadaolev piiratud rühma tüüp?

Cohen ja Lenstra õhutasid arvuteoreetikuid kaaluma mitte ainult üksikuid näiteid klassirühmade kohta, vaid statistikat, mis on klassirühmade kui terviku aluseks. Nende ennustused lõid nägemuse matemaatikast kui universumist, mille mustrid tuleb paljastada igal tasandil.

Peaaegu 40 aastat hiljem arvatakse, et Cohen-Lenstra heuristika vastab tõele, kuigi keegi pole jõudnud selle tõestuseni. Nende mõju matemaatikale on olnud käegakatsutav, ütles Madisoni osariigi Wisconsini ülikooli emeriitprofessor Nigel Boston. "See, mis on avastatud, on see hämmastav veeb," ütles ta. "Seal on tohutu infrastruktuur, kuidas me arvame, et maailm on kokku pandud."

Ainuke mäng linnas

Kuna matemaatikud ei suutnud heuristikaga otseselt tegeleda, tulid nad välja paremini lahendatavate probleemidega, mis lootsid olukorda valgustada. Sellest tööst selgus kasulik kogum suurusi, mida matemaatikud hakkasid tõenäosusteoorias kasutatava termini järgi hetkedeks nimetama.

Tõenäoliselt võivad hetked aidata teil juhuslike arvude taga olevaid jaotusi välja mõelda. Mõelge näiteks 1. jaanuari päeva kõrge temperatuuri jaotusele New Yorgis – tõenäosus, et järgmise aasta 1. jaanuaril on see 10 kraadi Fahrenheiti või 40 kraadi või 70 või 120 kraadi. Peate ainult töötama koos on minevikuandmed: iga aasta 1. jaanuari päeva rekordi ajalugu alates salvestatud ajaloo algusest.

Kui arvutate nende temperatuuride keskmise, saate teada natuke, kuid mitte kõike. Keskmine kõrge 40 kraadine temperatuur ei näita võimalust, et temperatuur on üle 50 kraadi või alla 20 kraadi.

Kuid see muutub, kui teile antakse rohkem teavet. Täpsemalt võite õppida temperatuuri ruudu keskmist, suurust, mida nimetatakse jaotuse teiseks momendiks. (Keskmine on esimene hetk.) Või võite õppida kuubikute keskmist, mida tuntakse kolmanda hetkena, või neljanda astme keskmist – neljandat hetke.

1920. aastateks olid matemaatikud aru saanud, et kui hetked selles seerias kasvavad piisavalt aeglaselt, siis kõigi hetkede teadmine võimaldab järeldada, et ainult ühes võimalikus jaotuses on need hetked. (Kuigi see ei võimalda teil seda jaotust tingimata otseselt arvutada.)

"See on tõesti ebaintuitiivne," ütles Wood. "Kui mõelda pidevale jaotusele, on sellel mingi kuju. Tundub, et sellel on enamat kui lihtsalt numbrite jadasse jäädvustada.

Cohen-Lenstra heuristikast huvitatud matemaatikud leidsid, et nii nagu tõenäosusteooria momente saab kasutada tõenäosusjaotuse saamiseks, võivad klassirühmade jaoks teatud viisil määratletud hetked olla objektiiviks, mille kaudu näeme nende suurust ja struktuuri. . Toronto ülikooli matemaatik Jacob Tsimerman ütles, et ta ei kujuta ette, kuidas saaks klassirühmade suuruse jaotust otseselt välja arvutada. Tema sõnul on hetkede kasutamine "rohkem kui lihtsam. See on ainuke mäng linnas."

See maagiline hetk

Kuigi iga tõenäosusmoment on seotud täisarvuga – kolmanda astme, neljanda astmega ja nii edasi – vastavad arvuteoreetikute poolt kasutusele võetud uued kogused rühmale. Need uued hetked sõltuvad asjaolust, et sageli saate grupi taandada väiksemaks rühmaks, alandades erinevad elemendid kokku.

Grupiga seotud hetke arvutamiseks G, võtke kõik võimalikud klassirühmad – üks iga uue ruutjuure kohta, mille lisate täisarvudele. Loendage iga klassirühma jaoks kokku mitu erinevat viisi, milleks saate selle ahendada G. Seejärel võtke nende arvude keskmine. See protsess võib tunduda keeruline, kuid sellega on palju lihtsam töötada kui Coheni ja Lenstra ennustuste tegelik jaotus. Kuigi Cohen-Lenstra heuristikat ise on keeruline väita, on nende prognoositavad jaotuse hetked kõik 1.

"See paneb mõtlema, et vau, võib-olla on hetked loomulik viis sellele läheneda," ütles Ellenberg. "Tundub usutavam tõestada, et miski on võrdne 1-ga, kui tõestada, et see võrdub mingi hullumeelse lõpmatu tootega."

Kui matemaatikud uurivad jaotust rühmade (klassirühmade või muul viisil) vahel, saavad nad iga rühma jaoks võrrandi G, kusjuures tõenäosused esindavad nüüd näiteks selliste klassirühmade osakaalu, mis näevad välja nagu $latex mathbb{Z}/3mathbb{Z}$. Lõpmatult paljude võrrandite ja lõpmatult paljude võimalike klassirühmadega on tõenäosuste lahendamine keeruline. Pole ilmselge, et seda on isegi mõtet teha.

"Kui teil on lõpmatuid summasid, võivad asjad valesti minna," ütles Wood.

Kuid matemaatikud, kes ei leidnud endiselt jaotuste uurimiseks teisi teid, pöördusid pidevalt hetkeprobleemi juurde. aastal avaldatud töös Matemaatika aastaraamatud aastal 2016 Ellenberg koos Akshay Venkateshi ja Craig Westerlandiga, kasutatud hetked klassirühmade statistikat uurida veidi teises keskkonnas, kui Cohen ja Lenstra olid arvestanud. See idee oli taaskasutatud mitu korda. Kuid iga kord, kui teadlased neid hetki kasutasid, tuginesid nad oma konkreetse probleemi veidrustele, et tõestada, et lõpmatul võrrandikogumil on lahendus. See tähendas, et nende tehnikad ei olnud ülekantavad. Järgmine matemaatik, kes vajab hetkede kasutamist, peaks hetkeülesande uuesti lahendama.

Koostöö alguses plaanisid Sawin ja Wood samuti seda teed minna. Nad kasutasid hetki, et ennustada, kuidas klassirühmade keerulisemaid versioone levitati. Kuid umbes aasta pärast oma projekti pöörasid nad oma tähelepanu hetkeprobleemile endale.

Kõrvaljälgede saamine

Kolleegid kirjeldavad Sawinit ja Woodi kui ebatavaliselt kirglikke oma töösse. "Nad on mõlemad väga targad. Kuid seal on palju nutikaid inimesi, ”ütles Zureick-Brown. "Neil on lihtsalt positiivne suhtumine matemaatika tegemisesse."

Algselt soovisid Sawin ja Wood kasutada hetki, et laiendada Cohen-Lenstra ennustusi uutele seadetele. Kuid peagi muutusid nad oma hetkeprobleemivaidlusega rahulolematuks. "Meil oli vaja sarnaseid argumente korduvalt kirjutada," meenutas Sawin. Veelgi enam, lisas ta, et matemaatiline keel, mida nad kasutasid, "ei tundunud olevat argumendi keskmes... Ideed olid olemas, kuid me lihtsalt ei leidnud õiget viisi nende väljendamiseks."

Sawin ja Wood süvenesid oma tõestusse, püüdes aru saada, mis selle kõige all tegelikult peitub. Nad said lõpuks tõendi, mis lahendas hetkeprobleemi mitte ainult nende konkreetse rakenduse, vaid mis tahes rühmade jaotuse jaoks - ja igasuguste muude matemaatiliste struktuuride jaoks.

Nad jagavad probleemi väikesteks juhitavateks sammudeks. Selle asemel, et kogu tõenäosusjaotust ühe korraga lahendada, keskendusid nad vaid väikesele lõigule hetkedest.

Näiteks rühmade tõenäosusjaotuse hetkeprobleemi lahendamiseks seostatakse iga hetk rühmaga G. Algul vaatasid Sawin ja Wood võrrandisüsteemi, mis sisaldas ainult piiratud rühmade loendi momente. Seejärel lisasid nad loendisse aeglaselt rühmi, vaadates iga kord üha rohkem hetki. Probleemi järk-järgult keerukamaks muutes muutsid nad iga sammu lahendatavaks probleemiks. Vähehaaval leidsid nad hetkeprobleemi täieliku lahenduse.

"See fikseeritud nimekiri sarnaneb prillidega, mille paned ette, ja mida rohkemate gruppidega olete nõus arvestama, seda paremad on teie prillid," selgitas Wood.

Kui nad lõpuks viimased kõrvalised detailid tolmu maha pühkisid, leidsid nad end vaidlusest, mille kõõlused ulatusid üle matemaatika. Nende tulemus töötas klassirühmade, geomeetriliste kujunditega seotud rühmade, punktide ja joonte võrgustike, aga ka muude matemaatilisema keerukusega komplektide puhul. Kõigis neis olukordades leidsid Sawin ja Wood valemi, mis võtab hetkede komplekti ja sülitab välja jaotuse, millel on need hetked (muude nõuete hulgas seni, kuni hetked ei kasva liiga kiiresti).

"See on vägagi Melanie stiilis," ütles Ellenberg. "Tõestame väga üldist teoreemi, mis käsitleb paljusid erinevaid juhtumeid omamoodi ühtlaselt ja elegantselt."

Sawin ja Wood lähevad nüüd tagasi oma algse eesmärgi juurde. Jaanuari alguses jagasid nad uus paber mis parandab ekslikud Cohen-Lenstra ennustused 1980. aastate lõpus tegi Cohen ja tema kolleeg Jacques Martinet. Peale selle on neil järjekorras veel rohkem tulemusi, plaanides laiendada heuristikat veelgi uutele olukordadele. "Ma ei tea, kas see projekt kunagi lõpeb," ütles Sawin.

Hetkeline probleem, mille Sawin ja Wood lahendasid, on olnud "omamoodi okas teie peas paljude erinevate küsimuste jaoks," ütles Tsimerman. "Ma arvan, et paljud matemaatikud hingavad kergendatult."