Matematikai trükkök a középtáv megszelídítéséhez | Quanta Magazin

Eddig ebben az évben, Quanta A Ramsey-elmélet három fő előrelépését ismertette, a matematikai minták létrehozásának elkerülésének tanulmányozását. A első eredmény új határt szabjon arra vonatkozóan, hogy mekkora lehet egy egész számkészlet anélkül, hogy három egyenlő távolságra lévő számot tartalmazna, például {2, 4, 6} vagy {21, 31, 41}. A második és a harmadik hasonlóképpen új korlátokat szab a hálózatok méretének olyan pontok klaszterei nélkül, amelyek vagy mind össze vannak kapcsolva, vagy mind el vannak választva egymástól.

A bizonyítékok arra vonatkoznak, hogy mi történik, amikor az érintett számok végtelenül nagyra nőnek. Paradox módon ez néha könnyebb lehet, mint a való világ bosszantó mennyiségeinek kezelése.

Vegyünk például két kérdést egy igazán nagy nevezőjű törttel kapcsolatban. Megkérdezheti, hogy mondjuk mi a decimális kiterjesztése az 1/42503312127361-nek. Vagy megkérdezheti, hogy ez a szám közelebb kerül-e a nullához, ahogy a nevező nő. Az első kérdés egy konkrét kérdés egy valós mennyiségre vonatkozóan, és nehezebb kiszámítani, mint a második, amely azt kérdezi, hogy a mennyiség hogyan 1/n „aszimptotikusan” változni fog n nő. (Egyre közelebb kerül a 0-hoz.)

„Ez az egész Ramsey-elméletet sújtó probléma” – mondta William Gasarch, a Marylandi Egyetem informatikusa. "A Ramsey-elmélet aszimptotikusan nagyon szép eredményekről ismert." De a végtelennél kisebb számok elemzéséhez teljesen más matematikai eszköztárra van szükség.

Gasarch olyan kérdéseket tanulmányozott a Ramsey-elméletben, amelyek olyan véges számokat tartalmaznak, amelyek túl nagyok ahhoz, hogy a problémát nyers erővel meg lehessen oldani. Az egyik projektben átvette az idei első áttörés véges változatát – egy februári tanulmányt. Zander Kelley, végzős hallgató az Illinoisi Egyetemen, Urbana-Champaign, és Raghu Meka a Los Angeles-i Kaliforniai Egyetemen. Kelley és Meka új felső korlátot talált arra vonatkozóan, hogy hány egész szám van 1 és között N halmazba helyezheti, miközben elkerüli a háromtagú progressziót vagy az egyenletesen elosztott számok mintáit.

Pedig Kelley és Meka eredménye akkor is érvényes, ha N viszonylag kicsi, ebben az esetben nem ad különösebben hasznos kötést. Nagyon kis érték esetén N, jobb, ha ragaszkodsz a nagyon egyszerű módszerekhez. Ha N ha mondjuk 5, nézd meg az összes lehetséges számkészletet 1 és XNUMX között N, és válassza ki a legnagyobb progressziómenteset: {1, 2, 4, 5}.

De a különböző lehetséges válaszok száma nagyon gyorsan növekszik, és túlságosan megnehezíti egy ilyen egyszerű stratégia alkalmazását. Több mint 1 millió halmaz létezik, amelyek 1 és 20 közötti számokból állnak. Több mint 10⁶⁰ 1 és 200 közötti számokat használva. A legjobb progressziómentes halmaz megtalálása ezekre az esetekre tetemes adag számítási teljesítményt igényel, még hatékonyságjavító stratégiák mellett is. „Sok teljesítményt kell tudni kicsikarni a dolgokból” – mondta James Glenn, a Yale Egyetem informatikusa. 2008-ban Gasarch, Glenn és Clyde Kruskal a Marylandi Egyetemen programot írt hogy megtalálja a legnagyobb progressziómentes készleteket egészen an N (Az előző munkák 187-re, valamint 150-re is válaszoltak.) A trükkök sora ellenére a programjuk befejezése hónapokig tartott, mondta Glenn.

Számítási terhelésük csökkentése érdekében a csapat egyszerű teszteket használt, amelyek megakadályozták, hogy a programjuk zsákutcás keresést folytasson, és kisebb részekre osztotta fel a készleteiket, amelyeket külön elemeztek.

Gasarch, Glenn és Kruskal számos más stratégiát is kipróbált. Az egyik ígéretes ötlet a véletlenszerűségre támaszkodott. A progressziómentes halmaz egyszerű módja az, hogy 1-et tesz a halmazba, majd mindig hozzáadja a következő számot, amely nem hoz létre aritmetikai sorozatot. Kövesse ezt az eljárást, amíg el nem éri a 10-es számot, és megkapja az {1, 2, 4, 5, 10} halmazt. De kiderült, hogy általában nem ez a legjobb stratégia. "Mi van, ha nem kezdjük 1-től?" – mondta Gasarch. "Ha egy véletlenszerű helyen kezdesz, jobban jársz." A kutatóknak fogalmuk sincs, miért olyan hasznos a véletlenszerűség – tette hozzá.

A másik két új Ramsey-elmélet eredményének véges változatának kiszámítása még bosszantóbb, mint a progressziómentes halmazok méretének meghatározása. Ezek az eredmények olyan matematikai hálózatokra vonatkoznak (úgynevezett gráfok), amelyek olyan csomópontokból állnak, amelyeket éleknek nevezett vonalak kötnek össze. A Ramsey-szám r(s, t). s csatlakoztatott csomópontok ill t szétkapcsoltak. A Ramsey-szám kiszámítása olyan fejfájást okoz, hogy még r(5, 5) ismeretlen – valahol 43 és 48 között van.

A 1981, Brendan McKay, aki jelenleg az Ausztrál Nemzeti Egyetem informatikusa, megírta a nauty nevű szoftvert, amely a Ramsey-számok kiszámítását volt hivatott egyszerűbbé tenni. A Nauty gondoskodik arról, hogy a kutatók ne vesztegessenek idejüket két olyan grafikon ellenőrzésére, amelyek egymásnak csak átfordított vagy elforgatott változatai. „Ha valaki a környéken tartózkodik, és nem használ nautint, akkor a játéknak vége. Használnod kell – mondta Stanisław Radziszowski, a Rochester Institute of Technology matematikusa. Ennek ellenére a számítások mennyisége szinte felfoghatatlan. 2013-ban Radziszowski ill Jan Goedgebeur bebizonyította r(3, 10) legfeljebb 42. „Azt hiszem, ez csaknem 50 CPU-évbe telt” – mondta Goedgebeur, a belgiumi KU Leuven Egyetem informatikusa.

Ha nem tud pontos Ramsey-számot kiszámítani, megpróbálhatja példákkal leszűkíteni az értékét. Ha találna egy 45 csomópontos gráfot öt csomópont nélkül, amelyek mindegyike össze volt kapcsolva, és öt csomópont nélkül, amelyek mind le vannak kapcsolva, az bizonyítaná, hogy r(5, 5) nagyobb, mint 45. A Ramsey-számokat tanulmányozó matematikusok korábban azt gondolták, hogy egyszerű lenne megtalálni ezeket a Ramsey-gráfoknak nevezett példákat, mondta Radziszowski. De nem így volt. „Az volt az elvárás, hogy a szép, klassz matematikai konstrukciók a lehető legjobb konstrukciókat adják, és csak több emberre van szükségünk, hogy dolgozzanak rajta” – mondta. "Egyre inkább az az érzésem, hogy kaotikus."

A véletlenszerűség a megértés akadálya és hasznos eszköze is. Geoffrey Exoo, az Indiana Állami Egyetem informatikusa éveket töltött azzal, hogy véletlenszerű módszereket finomítson Ramsey-gráfok előállításához. Ban ben 2015 papír Több tucat új, rekordot döntő Ramsey-gráf bejelentésekor Exoo és Milos Tatarevic véletlenszerű gráfokat generált, majd fokozatosan módosította azokat olyan élek törlésével vagy hozzáadásával, amelyek csökkentették a nem kívánt klaszterek számát, amíg nem találtak egy Ramsey-gráfot. Exoo technikái ugyanakkor művészet, mint bármi más, mondta Radziszowski. Néha megkövetelik tőle, hogy több módszert kombináljon, vagy ítélkezzen arról, hogy milyen grafikonokkal kezdje. „Sokan, sokan kipróbálják, de nem tudják megcsinálni” – mondta Radziszowski.

A Ramsey-gráfok generálására kifejlesztett technikák egy nap szélesebb körben is hasznosak lehetnek, mondta Goedgebeur, aki dolgozott rajta másfajta grafikonok készítése, például kémiai vegyületeket ábrázoló gráfok. „Nem valószínű, hogy ezek a technikák átvihetők és módosíthatók más grafikonosztályok hatékonyabb generálása érdekében (és fordítva)” – írta egy e-mailben.

Radziszowski számára azonban a kis Ramsey-számok tanulmányozásának oka sokkal egyszerűbb. „Mert nyitva van, mert senki sem tudja, mi a válasz” – mondta. „A triviális esetek, amelyeket kézzel csinálunk; egy kicsit nagyobb, kell egy számítógép, és egy kicsit nagyobb, még a számítógép sem elég jó. És így megjelenik a kihívás.”