Matematični triki za krotenje srednje razdalje | Revija Quanta

Doslej letos Quanta je zapisal tri velike napredke Ramseyjeve teorije, študije o tem, kako se izogniti ustvarjanju matematičnih vzorcev. The prvi rezultat na novo omejite, kako velik je lahko nabor celih števil, ne da bi vseboval tri enakomerno razporejena števila, kot so {2, 4, 6} ali {21, 31, 41}. The 2. in Tretji podobno postavili nove meje velikosti omrežij brez skupin točk, ki so bodisi vse povezane ali vse izolirane druga od druge.

Dokazi obravnavajo, kaj se zgodi, ko vpletene številke neskončno rastejo. Paradoksalno je, da je to lahko včasih lažje kot ukvarjanje z nadležnimi količinami v resničnem svetu.

Na primer, razmislite o dveh vprašanjih o ulomku z res velikim imenovalcem. Lahko se vprašate, kakšna je decimalna razširitev, na primer, 1/42503312127361. Lahko pa vprašate, ali se bo to število približalo ničli, ko se imenovalec povečuje. Prvo vprašanje je specifično vprašanje o dejanski količini in ga je težje izračunati kot drugo, ki sprašuje, kako količina 1/n se bo "asimptotično" spremenilo kot n raste. (Vse bližje se 0.)

"To je problem, ki pesti celotno Ramseyevo teorijo," je dejal William Gasarch, računalniški znanstvenik na Univerzi v Marylandu. "Ramseyeva teorija je znana po tem, da ima asimptotično zelo dobre rezultate." Toda analiziranje števil, ki so manjša od neskončnosti, zahteva povsem drugačno matematično orodje.

Gasarch je preučeval vprašanja Ramseyjeve teorije, ki vključujejo končna števila, ki so prevelika, da bi se problem rešil s surovo silo. V enem projektu se je lotil končne različice prvega od letošnjih prebojev – februarskega dokumenta avtorja Zander Kelley, podiplomski študent na Univerzi Illinois, Urbana-Champaign, in Raghu Meka Univerze v Kaliforniji, Los Angeles. Kelley in Meka sta našla novo zgornjo mejo za število celih števil med 1 in N lahko vstavite v niz, pri tem pa se izognete napredovanju treh členov ali vzorcem enakomerno razporejenih števil.

Čeprav rezultat Kelleyja in Meke velja tudi, če N razmeroma majhen, v tem primeru ne daje posebej uporabne meje. Za zelo majhne vrednosti N, je bolje, da se držite zelo preprostih metod. če N je recimo 5, samo poglejte vse možne nize števil med 1 in N, in izberite največjega brez napredovanja: {1, 2, 4, 5}.

Toda število različnih možnih odgovorov zelo hitro raste in je pretežko uporabiti tako preprosto strategijo. Obstaja več kot 1 milijon nizov, sestavljenih iz številk med 1 in 20. Obstaja več kot 10⁶⁰ z uporabo števil med 1 in 200. Iskanje najboljšega niza brez napredovanja za te primere zahteva velik odmerek računalniške moči, tudi s strategijami za izboljšanje učinkovitosti. "Iz stvari moraš biti sposoben iztisniti veliko zmogljivosti," je rekel James Glenn, računalniški znanstvenik na univerzi Yale. Leta 2008 so Gasarch, Glenn in Clyde Kruskal Univerze v Marylandu napisal program najti največje komplete brez napredovanja do an N od 187. (Prejšnje delo je dobilo odgovore do 150, pa tudi za 157.) Kljub seznamu trikov je njihov program trajal več mesecev, da je bil dokončan, je dejal Glenn.

Da bi zmanjšali računalniško obremenitev, je skupina uporabila preproste teste, ki so preprečili njihovemu programu iskanje v slepi ulici in razdelili njihove nize na manjše dele, ki so jih analizirali ločeno.

Gasarch, Glenn in Kruskal so poskusili tudi več drugih strategij. Ena obetavna ideja je temeljila na naključju. Preprost način, da dobite niz brez napredovanja, je, da v svoj niz vnesete 1, nato pa vedno dodate naslednje število, ki ne ustvarja aritmetičnega napredovanja. Sledite temu postopku, dokler ne dosežete številke 10, in dobili boste niz {1, 2, 4, 5, 10}. Toda izkazalo se je, da to na splošno ni najboljša strategija. "Kaj če ne začnemo ob 1?" je dejal Gasarch. "Če začneš na naključnem mestu, ti dejansko uspe." Raziskovalci nimajo pojma, zakaj je naključnost tako koristna, je dodal.

Izračun končnih različic dveh drugih novih rezultatov Ramseyjeve teorije je še bolj moteč kot določanje velikosti nizov brez napredovanja. Ti rezultati zadevajo matematična omrežja (imenovana grafi), sestavljena iz vozlišč, povezanih s črtami, imenovanimi robovi. Ramseyevo število r(s, t) je najmanjše število vozlišč, ki jih mora imeti graf, preden se postane nemogoče izogniti vključitvi katere koli skupine s povezanih vozlišč oz t odklopljeni. Računanje Ramseyeve številke je tako glavobol r(5, 5) ni znano — je nekje med 43 in 48.

V 1981, Brendan McKay, zdaj računalniški znanstvenik na Avstralski nacionalni univerzi, je napisal programsko opremo, imenovano nauty, ki naj bi poenostavila izračun Ramseyevih števil. Nauty zagotavlja, da raziskovalci ne izgubljajo časa s preverjanjem dveh grafov, ki sta samo obrnjeni ali zasukani različici drug drugega. »Če je nekdo v bližini in ne uporablja nesramnosti, je igre konec. Morate ga uporabiti," je rekel Stanisław Radziszowski, matematik na Rochester Institute of Technology. Kljub temu je količina vključenega računanja skoraj nerazumljiva. Leta 2013 sta Radziszowski in Jan Goedgebeur to dokazal r(3, 10) je največ 42. »Mislim, da je trajalo skoraj 50 CPU let,« je dejal Goedgebeur, računalniški znanstvenik na univerzi KU Leuven v Belgiji.

Če ne morete izračunati točnega Ramseyevega števila, lahko poskusite zožiti njegovo vrednost s primeri. Če bi našli graf s 45 vozlišči brez petih vozlišč, ki bi bila vsa povezana, in brez petih vozlišč, ki bi bila vsa nepovezana, bi to dokazovalo, r(5, 5) je večji od 45. Matematiki, ki so preučevali Ramseyeva števila, so mislili, da bo iskanje teh primerov, imenovanih Ramseyevi grafi, preprosto, je dejal Radziszowski. Ampak ni bilo tako. "Pričakovali smo, da bodo lepe, kul matematične konstrukcije dale najboljše možne konstrukcije, in potrebujemo samo več ljudi, ki bodo delali na tem," je dejal. "Čedalje bolj imam občutek, da je kaotično."

Naključnost je hkrati ovira za razumevanje in uporabno orodje. Geoffrey Exoo, računalničar na Državni univerzi Indiana, je leta izpopolnjeval naključne metode za ustvarjanje Ramseyevih grafov. notri papir 2015 ob napovedi na desetine novih, rekordnih Ramseyjevih grafov sta Exoo in Miloš Tatarević ustvarila naključne grafe in jih nato postopoma prilagodila z brisanjem ali dodajanjem robov, ki so zmanjšali število neželenih grozdov, dokler niso našli Ramseyevega grafa. Radziszowski je dejal, da so tehnike Exoo prav tako umetnost kot karkoli drugega. Včasih od njega zahtevajo, da kombinira več metod ali da presodi, s kakšnimi grafi naj začne. "Veliko, veliko ljudi to poskuša, a tega ne zmorejo," je dejal Radziszowski.

Tehnike, razvite za ustvarjanje Ramseyjevih grafov, bi lahko bile nekega dne bolj uporabne, je dejal Goedgebeur, ki je delal naprej ustvarjanje drugih vrst grafov, kot so grafi, ki predstavljajo kemične spojine. "Ni malo verjetno, da je mogoče te tehnike tudi prenesti in prilagoditi za pomoč pri ustvarjanju drugih razredov grafov učinkoviteje (in obratno)," je zapisal v elektronskem sporočilu.

Za Radziszowskega pa je razlog za preučevanje majhnih Ramseyjevih števil veliko preprostejši. "Ker je odprto, ker nihče ne ve, kaj je odgovor," je dejal. »Pomembni primeri, ki jih delamo ročno; malo večji, potrebuješ računalnik, in malo večji, tudi računalnik ni dovolj dober. In tako se pojavi izziv.«