Matemaattisia temppuja keskimatkan kesyttämiseen | Quanta-lehti

Tähän mennessä tänä vuonna, Quanta on kirjannut kolme suurta edistystä Ramseyn teoriassa, tutkimuksessa siitä, kuinka vältetään matemaattisten kuvioiden luominen. The ensimmäinen tulos aseta uusi raja sille, kuinka suuri kokonaislukujoukko voi olla ilman kolmea tasavälein sijoitettua numeroa, kuten {2, 4, 6} tai {21, 31, 41}. The toinen ja kolmas samoin asettaa uudet rajat verkkojen koolle ilman pisteiden klustereita, jotka ovat joko kaikki kytkettyjä tai kaikki eristettyjä toisistaan.

Todistukset käsittelevät sitä, mitä tapahtuu, kun mukana olevat luvut kasvavat äärettömän suuriksi. Paradoksaalista kyllä, tämä voi joskus olla helpompaa kuin ärsyttävien reaalimaailman määrien käsitteleminen.

Harkitse esimerkiksi kahta kysymystä murtoluvusta, jolla on todella suuri nimittäjä. Saatat kysyä, mikä on esimerkiksi luvun 1/42503312127361 desimaalilaajennus. Tai voit kysyä, tuleeko tämä luku lähemmäksi nollaa, kun nimittäjä kasvaa. Ensimmäinen kysymys on erityinen kysymys reaalimaailman suuresta, ja sitä on vaikeampi laskea kuin toinen, joka kysyy kuinka määrä 1/n muuttuu "asymptoottisesti" muodossa n kasvaa. (Se tulee lähemmäksi nollaa.)

"Tämä on ongelma, joka vaivaa koko Ramseyn teoriaa", sanoi William Gasarch, tietojenkäsittelytieteilijä Marylandin yliopistosta. "Ramseyn teoria tunnetaan asymptoottisesti erittäin hyvistä tuloksista." Mutta ääretöntä pienempien lukujen analysointi vaatii täysin erilaisen matemaattisen työkalupaketin.

Gasarch on tutkinut Ramseyn teorian kysymyksiä, joihin liittyy äärellisiä lukuja, jotka ovat liian suuria ongelman ratkaisemiseksi raa'alla voimalla. Yhdessä projektissa hän otti rajallisen version tämän vuoden ensimmäisistä läpimurroista – helmikuun julkaisusta Zander Kelley, jatko-opiskelija Illinoisin yliopistossa Urbana-Champaignissa ja Raghu Meka Kalifornian yliopistosta, Los Angelesista. Kelley ja Meka löysivät uuden ylärajan sille, kuinka monta kokonaislukua välillä 1 ja N voit laittaa joukoksi välttäen kolmen termin etenemistä tai tasaisin välein olevien numeroiden kuvioita.

Vaikka Kelleyn ja Mekan tulos pätee vaikka N on suhteellisen pieni, se ei anna tässä tapauksessa erityisen hyödyllistä rajaa. Hyvin pienille arvoille N, sinun kannattaa pitää kiinni hyvin yksinkertaisista menetelmistä. Jos N on esimerkiksi 5, katso vain kaikkia mahdollisia lukujoukkoja välillä 1 ja N, ja valitse suurin etenemätön: {1, 2, 4, 5}.

Mutta erilaisten vastausvaihtoehtojen määrä kasvaa hyvin nopeasti ja tekee näin yksinkertaisen strategian käyttämisestä liian vaikeaa. On olemassa yli miljoona joukkoa, jotka koostuvat numeroista 1-1. Niitä on yli 20⁶⁰ käyttämällä numeroita 1 ja 200 välillä. Parhaan etenemisvapaan joukon löytäminen näihin tapauksiin vaatii reilun annoksen laskentatehoa jopa tehokkuutta parantavilla strategioilla. "Sinun täytyy pystyä puristamaan asioista paljon suorituskykyä", sanoi James Glenn, tietojenkäsittelytieteilijä Yalen yliopistosta. Vuonna 2008 Gasarch, Glenn ja Clyde Kruskal Marylandin yliopistosta kirjoitti ohjelman löytääksesi suurimmat etenemättömät setit aina N 187. (Aiemmat työt olivat saaneet vastauksia jopa 150:een, samoin kuin 157:ään.) Huolimatta temppujen luettelosta, heidän ohjelmansa valmistuminen kesti kuukausia, Glenn sanoi.

Laskentakuormituksen vähentämiseksi ryhmä käytti yksinkertaisia ​​testejä, jotka estivät ohjelmaa suorittamasta umpikujahakuja ja jakoivat joukonsa pienempiin osiin, jotka he analysoivat erikseen.

Gasarch, Glenn ja Kruskal kokeilivat myös useita muita strategioita. Yksi lupaava idea perustui sattumanvaraisuuteen. Yksinkertainen tapa muodostaa etenemisvapaa joukko on lisätä joukkoon 1 ja lisätä sitten aina seuraava numero, joka ei luo aritmeettista etenemistä. Noudata tätä menettelyä, kunnes osut numeroon 10, ja saat joukon {1, 2, 4, 5, 10}. Mutta käy ilmi, että tämä ei ole paras strategia yleisesti. "Entä jos emme aloita yhdeltä?" Gasarch sanoi. "Jos aloitat satunnaisesta paikasta, pärjäät paremmin." Tutkijoilla ei ole aavistustakaan, miksi satunnaisuus on niin hyödyllistä, hän lisäsi.

Kahden muun uuden Ramseyn teoriatuloksen äärellisten versioiden laskeminen on vieläkin kiusallisempaa kuin etenemisvapaiden joukkojen koon määrittäminen. Nämä tulokset koskevat matemaattisia verkkoja (kutsutaan graafiksi), jotka koostuvat solmuista, jotka on yhdistetty reunoiksi kutsutuilla viivoilla. Ramseyn numero r(s, t) on pienin määrä solmuja, jotka graafissa on oltava, ennen kuin on mahdotonta välttää jommankumman ryhmän sisällyttämistä s liitetyt solmut tai t irrotetut. Ramseyn numero on niin päänsärky laskea, että jopa r(5, 5) on tuntematon - se on jossain 43 ja 48 välillä.

Vuonna 1981, Brendan McKay, nykyään tietotekniikan tutkija Australian kansallisessa yliopistossa, kirjoitti nauty-nimisen ohjelmiston, jonka tarkoituksena oli tehdä Ramsey-lukujen laskemisesta yksinkertaisempaa. Nauty varmistaa, että tutkijat eivät tuhlaa aikaa kahden kaavion tarkistamiseen, jotka ovat vain käännettyjä tai kierrettyjä versioita toisistaan. ”Jos joku on alueella eikä käytä nautsia, peli on ohi. Sinun täytyy käyttää sitä", sanoi Stanisław Radziszowski, matemaatikko Rochester Institute of Technologyssa. Silti laskennan määrä on lähes käsittämätön. Vuonna 2013 Radziszowski ja Jan Goedgebeur todistanut sen r(3, 10) on enintään 42. "Se kesti mielestäni lähes 50 CPU vuotta", sanoi Goedgebeur, tietojenkäsittelytieteilijä KU Leuvenin yliopistosta Belgiassa.

Jos et pysty laskemaan tarkkaa Ramsey-lukua, voit yrittää kaventaa sen arvoa esimerkein. Jos löytäisit 45 solmun graafin ilman viittä solmua, jotka kaikki olivat yhteydessä, ja ilman viittä solmua, jotka kaikki olivat irrotettuja, se todistaisi, että r(5, 5) on suurempi kuin 45. Ramsey-lukuja tutkivat matemaatikot ajattelivat, että näiden esimerkkien, nimeltään Ramsey-graafit, löytäminen olisi yksinkertaista, Radziszowski sanoi. Mutta se ei ollut niin. "Odotettiin, että hienot, siistit matemaattiset rakenteet antavat parhaat mahdolliset konstruktiot, ja tarvitsemme vain lisää ihmisiä työskentelemään sen parissa", hän sanoi. "Minun tunteeni on yhä enemmän se kaoottinen."

Satunnaisuus on sekä ymmärryksen este että hyödyllinen työkalu. Geoffrey Exoo, tietotekniikan tutkija Indianan osavaltion yliopistosta, on käyttänyt vuosia jalostaakseen satunnaisia ​​menetelmiä Ramsey-kaavioiden luomiseksi. Sisään 2015-paperi Exoo ja Milos Tatarevic ilmoittivat kymmenistä uusista, ennätyksellisistä Ramsey-kaavioista, loivat satunnaisia ​​kaavioita ja säätelivät niitä sitten vähitellen poistamalla tai lisäämällä reunoja, jotka vähensivät ei-toivottujen klustereiden määrää, kunnes he löysivät Ramsey-graafin. Exoon tekniikat ovat kuitenkin yhtä taidetta kuin mikä tahansa, Radziszowski sanoi. Joskus ne vaativat häntä yhdistämään useita menetelmiä tai käyttämään harkintaa siitä, millaisilla kaavioilla aloittaa. "Monet, monet ihmiset yrittävät sitä, eivätkä he voi tehdä sitä", Radziszowski sanoi.

Ramsey-kaavioiden luomiseen kehitetyt tekniikat voisivat joskus olla laajemminkin hyödyllisiä, sanoi Goedgebeur, joka on työskennellyt tuottaa muunlaisia ​​kaavioita, kuten kaavioita, jotka edustavat kemiallisia yhdisteitä. "Ei ole epätodennäköistä, että näitä tekniikoita voidaan myös siirtää ja mukauttaa muiden kaavioluokkien luomiseksi tehokkaammin (ja päinvastoin), hän kirjoitti sähköpostissa.

Radziszowskille syy pienten Ramsey-lukujen tutkimiseen on kuitenkin paljon yksinkertaisempi. "Koska se on avoin, koska kukaan ei tiedä, mikä vastaus on", hän sanoi. "Tyhteät tapaukset, joita teemme käsin; hieman suurempi, tarvitset tietokoneen, ja hieman suurempi, vaikka tietokone ei ole tarpeeksi hyvä. Ja niin haaste syntyy."