Trucchi matematici per domare la media distanza | Rivista Quanta

Finora quest'anno, Quanta ha raccontato tre importanti progressi nella teoria di Ramsey, lo studio di come evitare di creare schemi matematici. IL primo risultato metti un nuovo limite su quanto può essere grande un insieme di numeri interi senza contenere tre numeri equidistanti, come {2, 4, 6} o {21, 31, 41}. IL secondo ed Terzo allo stesso modo, poniamo nuovi limiti alla dimensione delle reti senza cluster di punti che sono tutti connessi o tutti isolati l'uno dall'altro.

Le prove affrontano ciò che accade man mano che i numeri coinvolti crescono infinitamente grandi. Paradossalmente, questo a volte può essere più facile che affrontare fastidiose quantità del mondo reale.

Ad esempio, considera due domande su una frazione con un denominatore molto grande. Potresti chiedere qual è l'espansione decimale di, diciamo, 1/42503312127361. Oppure potresti chiedere se questo numero si avvicinerà allo zero man mano che il denominatore cresce. La prima domanda è una domanda specifica su una quantità del mondo reale ed è più difficile da calcolare rispetto alla seconda, che chiede come la quantità 1/n cambierà "asintoticamente" come n cresce. (Si avvicina sempre di più a 0.)

"Questo è un problema che affligge tutta la teoria di Ramsey", ha detto Guglielmo Gasarco, un informatico dell'Università del Maryland. "La teoria di Ramsey è nota per avere risultati asintoticamente molto buoni." Ma l'analisi di numeri più piccoli dell'infinito richiede strumenti matematici completamente diversi.

Gasarch ha studiato questioni nella teoria di Ramsey che coinvolgono numeri finiti che sono troppo grandi perché il problema possa essere risolto con la forza bruta. In un progetto, ha assunto la versione finita della prima scoperta di quest'anno, un articolo di febbraio di Zander Kelley, uno studente laureato presso l'Università dell'Illinois, Urbana-Champaign, e Raghu Meka dell'Università della California, Los Angeles. Kelley e Meka hanno trovato un nuovo limite superiore su quanti numeri interi tra 1 e N puoi inserire in un set evitando progressioni a tre termini o schemi di numeri equidistanti.

Sebbene il risultato di Kelley e Meka si applichi anche se N è relativamente piccolo, non fornisce un limite particolarmente utile in quel caso. Per valori molto piccoli di N, è meglio attenersi a metodi molto semplici. Se N è, diciamo, 5, guarda tutte le possibili serie di numeri tra 1 e Ne scegli quello più grande senza progressione: {1, 2, 4, 5}.

Ma il numero di diverse risposte possibili cresce molto rapidamente e rende troppo difficile impiegare una strategia così semplice. Ci sono più di 1 milione di serie composte da numeri compresi tra 1 e 20. Ce ne sono più di 10⁶⁰ utilizzando numeri compresi tra 1 e 200. Trovare il miglior set senza progressione per questi casi richiede una notevole dose di potenza di calcolo, anche con strategie di miglioramento dell'efficienza. "Devi essere in grado di spremere molte prestazioni dalle cose", ha detto James Glenn, un informatico della Yale University. Nel 2008, Gasarch, Glenn e Clyde Kruskal dell'Università del Maryland ha scritto un programma per trovare i più grandi set senza progressione fino a un N di 187. (Il lavoro precedente aveva ottenuto le risposte fino a 150, così come per 157.) Nonostante un elenco di trucchi, il loro programma ha impiegato mesi per finire, ha detto Glenn.

Per ridurre il loro carico computazionale, il team ha utilizzato semplici test che hanno impedito al loro programma di perseguire ricerche senza uscita e ha suddiviso i loro set in parti più piccole che hanno analizzato separatamente.

Gasarch, Glenn e Kruskal hanno provato anche diverse altre strategie. Un'idea promettente si basava sulla casualità. Un modo semplice per creare un set senza progressione è inserire 1 nel tuo set, quindi aggiungere sempre il numero successivo che non crea una progressione aritmetica. Segui questa procedura fino a raggiungere il numero 10 e otterrai il set {1, 2, 4, 5, 10}. Ma si scopre che questa non è la migliore strategia in generale. "E se non iniziamo da 1?" disse Gasarco. "Se inizi da un posto a caso, in realtà fai meglio." I ricercatori non hanno idea del perché la casualità sia così utile, ha aggiunto.

Calcolare le versioni finite degli altri due nuovi risultati della teoria di Ramsey è ancora più fastidioso che determinare la dimensione degli insiemi senza progressione. Questi risultati riguardano reti matematiche (chiamate grafi) costituite da nodi collegati da linee chiamate spigoli. Il numero di Ramsey r(s, t) è il più piccolo numero di nodi che un grafo deve avere prima che diventi impossibile evitare di includere un gruppo di s nodi connessi o t quelli disconnessi. Il numero di Ramsey è un tale mal di testa da calcolare anche r(5, 5) è sconosciuto — è da qualche parte tra 43 e 48.

Nel 1981, Brendan McKay, ora scienziato informatico presso l'Australian National University, ha scritto un programma software chiamato nauty, che aveva lo scopo di rendere più semplice il calcolo dei numeri di Ramsey. Nauty assicura che i ricercatori non perdano tempo a controllare due grafici che sono solo versioni capovolte o ruotate l'una dell'altra. “Se qualcuno è in zona e non usa nauty, il gioco è finito. Devi usarlo”, disse Stanisław Radziszowski, un matematico del Rochester Institute of Technology. Tuttavia, la quantità di calcolo coinvolta è quasi incomprensibile. Nel 2013, Radziszowski e Jan Goedgebeur lo ha dimostrato r(3, 10) è al massimo 42. "Ci sono voluti, credo, quasi 50 anni di CPU", ha detto Goedgebeur, un informatico della KU Leuven University in Belgio.

Se non riesci a calcolare un numero di Ramsey esatto, puoi provare a restringere il valore con degli esempi. Se trovassi un grafico a 45 nodi senza cinque nodi che erano tutti connessi e senza cinque nodi che erano tutti disconnessi, ciò dimostrerebbe che r(5, 5) è maggiore di 45. I matematici che studiavano i numeri di Ramsey pensavano che trovare quegli esempi, chiamati grafi di Ramsey, sarebbe stato semplice, ha detto Radziszowski. Ma non è stato così. "C'era questa aspettativa che costruzioni matematiche belle e interessanti fornissero le migliori costruzioni possibili, e abbiamo solo bisogno di più persone che ci lavorino", ha detto. "La mia sensazione è sempre più caotica."

La casualità è sia un ostacolo alla comprensione che uno strumento utile. Geoffrey Exoo, un informatico dell'Indiana State University, ha passato anni a perfezionare metodi casuali per generare grafici di Ramsey. In una carta 2015 annunciando dozzine di nuovi grafici Ramsey da record, Exoo e Milos Tatarevic hanno generato grafici casuali e poi li hanno gradualmente modificati eliminando o aggiungendo bordi che hanno ridotto il numero di cluster indesiderati fino a quando non hanno trovato un grafico Ramsey. Le tecniche di Exoo sono più un'arte che altro, però, ha detto Radziszowski. A volte gli richiedono di combinare più metodi o di usare il giudizio su quale tipo di grafici iniziare. "Molte, molte persone lo provano e non possono farlo", ha detto Radziszowski.

Le tecniche sviluppate per generare i grafici di Ramsey potrebbero essere più ampiamente utili un giorno, ha detto Goedgebeur, che ha Lavorato su produrre altri tipi di grafici, come i grafici che rappresentano composti chimici. "Non è improbabile che queste tecniche possano anche essere trasferite e adattate per aiutare a generare altre classi di grafici in modo più efficiente (e viceversa)", ha scritto in una e-mail.

Per Radziszowski, tuttavia, la ragione per studiare i piccoli numeri di Ramsey è molto più semplice. "Perché è aperto, perché nessuno sa quale sia la risposta", ha detto. “I casi banali li facciamo a mano; un po 'più grande, hai bisogno di un computer, e un po' più grande, anche il computer non è abbastanza buono. E così emerge la sfida”.