Trucuri matematice pentru îmblânzirea distanței de mijloc | Revista Quanta

Până acum anul acesta, Cuante a descris trei progrese majore în teoria Ramsey, studiul modului de a evita crearea de modele matematice. The primul rezultat puneți o nouă limită asupra cât de mare poate fi un set de numere întregi fără a conține trei numere spațiate uniform, cum ar fi {2, 4, 6} sau {21, 31, 41}. The al doilea și al treilea în mod similar, puneți noi limite pentru dimensiunea rețelelor fără grupuri de puncte care sunt fie toate conectate, fie toate izolate unele de altele.

Dovezile se referă la ceea ce se întâmplă pe măsură ce numerele implicate cresc infinit de mari. În mod paradoxal, acest lucru poate fi uneori mai ușor decât a face față unor cantități deranjante din lumea reală.

De exemplu, luați în considerare două întrebări despre o fracție cu un numitor foarte mare. S-ar putea să vă întrebați care este expansiunea zecimală a, de exemplu, 1/42503312127361. Sau ați putea întreba dacă acest număr se va apropia de zero pe măsură ce numitorul crește. Prima întrebare este o întrebare specifică despre o cantitate din lumea reală și este mai greu de calculat decât a doua, care întreabă cum este cantitatea 1/n se va schimba „asimptotic” ca n dezvoltă. (Se apropie din ce în ce mai mult de 0.)

„Aceasta este o problemă care afectează toată teoria Ramsey”, a spus William Gasarch, un informatician la Universitatea din Maryland. „Teoria Ramsey este cunoscută pentru că are rezultate foarte bune asimptotic.” Dar analiza numerelor care sunt mai mici decât infinitul necesită o cutie de instrumente matematică complet diferită.

Gasarch a studiat întrebări din teoria Ramsey care implică numere finite care sunt prea mari pentru ca problema să fie rezolvată prin forță brută. Într-un proiect, el a preluat versiunea finită a primei descoperiri din acest an - un articol din februarie de Zander Kelley, un student absolvent la Universitatea din Illinois, Urbana-Champaign, și Raghu Meka de la Universitatea din California, Los Angeles. Kelley și Meka au găsit o nouă limită superioară pentru câte numere întregi între 1 și N puteți pune într-un set evitând în același timp progresiile pe trei termeni sau modelele de numere uniform distanțate.

Deși rezultatul lui Kelley și Meka se aplică chiar dacă N este relativ mic, nu oferă o limită deosebit de utilă în acest caz. Pentru valori foarte mici de N, mai bine te ții de metode foarte simple. Dacă N este, să zicem, 5, doar uită-te la toate seturile posibile de numere între 1 și Nși alegeți-l pe cel mai mare fără progresie: {1, 2, 4, 5}.

Dar numărul de răspunsuri posibile diferite crește foarte repede și face prea dificilă folosirea unei strategii atât de simple. Există mai mult de 1 milion de seturi formate din numere între 1 și 20. Există peste 10⁶⁰ folosind numere între 1 și 200. Găsirea celui mai bun set fără progresie pentru aceste cazuri necesită o doză mare de putere de calcul, chiar și cu strategii de îmbunătățire a eficienței. „Trebuie să fii capabil să strângi multă performanță din lucruri”, a spus James Glenn, un informatician la Universitatea Yale. În 2008, Gasarch, Glenn și Clyde Kruskal de la Universitatea din Maryland a scris un program pentru a găsi cele mai mari seturi fără progresie până la un N de 187. (Lucrările anterioare au primit răspunsuri până la 150, precum și pentru 157.) În ciuda unei liste de trucuri, programul lor a durat luni pentru a se termina, a spus Glenn.

Pentru a-și reduce sarcina de calcul, echipa a folosit teste simple care au împiedicat programul lor să urmărească căutări fără margini și a împărțit seturile în părți mai mici pe care le-au analizat separat.

Gasarch, Glenn și Kruskal au încercat și alte câteva strategii. O idee promițătoare s-a sprijinit pe aleatoriu. O modalitate simplă de a veni cu un set fără progresie este să puneți 1 în setul dvs., apoi să adăugați întotdeauna următorul număr care nu creează o progresie aritmetică. Urmați această procedură până când atingeți numărul 10 și veți obține setul {1, 2, 4, 5, 10}. Dar se pare că aceasta nu este cea mai bună strategie în general. „Dacă nu începem de la 1?” spuse Gasarch. „Dacă începi dintr-un loc la întâmplare, de fapt te descurci mai bine.” Cercetătorii habar n-au de ce aleatorierea este atât de utilă, a adăugat el.

Calcularea versiunilor finite ale celorlalte două rezultate noi ale teoriei Ramsey este chiar mai supărătoare decât determinarea mărimii seturilor fără progresie. Aceste rezultate se referă la rețele matematice (numite grafice) formate din noduri conectate prin linii numite muchii. Numărul Ramsey r(s, t) este cel mai mic număr de noduri pe care trebuie să-l aibă un grafic înainte de a deveni imposibil de evitat includerea fie a unui grup s noduri conectate sau t cele deconectate. Numărul Ramsey este o bătaie de cap atât de mare să-l calculezi r(5, 5) este necunoscut - este undeva între 43 și 48.

În 1981, Brendan McKay, acum un informatician la Universitatea Națională Australiană, a scris un program software numit nauty, care avea scopul de a simplifica calcularea numerelor Ramsey. Nauty se asigură că cercetătorii nu pierd timpul verificând două grafice care sunt doar versiuni inversate sau rotite unul ale celuilalt. „Dacă cineva este în zonă și nu folosește Naty, jocul s-a terminat. Trebuie să-l folosești”, a spus Stanisław Radziszowski, matematician la Institutul de Tehnologie Rochester. Cu toate acestea, cantitatea de calcul implicată este aproape de neînțeles. În 2013, Radziszowski și Jan Goedgebeur a dovedit că r(3, 10) este cel mult 42. „Cred că a fost nevoie de aproape 50 de ani CPU”, a spus Goedgebeur, un informatician la Universitatea KU Leuven din Belgia.

Dacă nu puteți calcula un număr Ramsey exact, puteți încerca să restrângeți valoarea acestuia cu exemple. Dacă ați găsi un grafic cu 45 de noduri fără cinci noduri care au fost toate conectate și fără cinci noduri care au fost toate deconectate, asta ar dovedi că r(5, 5) este mai mare decât 45. Matematicienii care studiază numerele Ramsey obișnuiau să creadă că găsirea acestor exemple, numite grafice Ramsey, ar fi simplă, a spus Radziszowski. Dar nu a fost așa. „Există această așteptare că construcțiile matematice frumoase și cool vor oferi cele mai bune construcții posibile și avem nevoie doar de mai mulți oameni care să lucreze la el”, a spus el. „Sentimentul meu este din ce în ce mai mult că este haotic.”

Aleatoria este atât un obstacol în calea înțelegerii, cât și un instrument util. Geoffrey Exoo, un informatician la Universitatea de Stat din Indiana, a petrecut ani de zile rafinând metode aleatorii pentru a genera grafice Ramsey. În o hârtie 2015 anunțând zeci de noi grafice Ramsey, care bat record, Exoo și Milos Tatarevic au generat grafice aleatoare și apoi le-au modificat treptat, ștergând sau adăugând margini care au redus numărul de clustere nedorite până când au găsit un grafic Ramsey. Totuși, tehnicile lui Exoo sunt la fel de mult o artă ca orice, a spus Radziszowski. Uneori îi cer să combine mai multe metode sau să judece cu ce fel de grafice să înceapă. „Mulți, mulți oameni o încearcă și nu o pot face”, a spus Radziszowski.

Tehnicile dezvoltate pentru a genera grafice Ramsey ar putea fi mai larg utile într-o zi, a spus Goedgebeur, care a lucrat la producând alte tipuri de grafice, cum ar fi grafice care reprezintă compuși chimici. „Nu este puțin probabil ca aceste tehnici să poată fi, de asemenea, transferate și ajustate pentru a ajuta la generarea altor clase de grafice mai eficient (și invers)”, a scris el într-un e-mail.

Pentru Radziszowski, însă, motivul studierii numerelor Ramsey mici este mult mai simplu. „Pentru că este deschis, pentru că nimeni nu știe care este răspunsul”, a spus el. „Cazurile banale le facem manual; puțin mai mare, aveți nevoie de un computer și puțin mai mare, chiar și computerul nu este suficient de bun. Și astfel apare provocarea.”