L’illegalità dei grandi numeri

La versione originale Di questa storia apparso in Rivista Quanta.

Finora quest’anno, Quanti ha raccontato tre importanti progressi nella teoria di Ramsey, lo studio di come evitare di creare schemi matematici. Il primo risultato pone un nuovo limite a quanto può essere grande un insieme di numeri interi senza contenere tre numeri equidistanti, come {2, 4, 6} o {21, 31, 41}. Analogamente, il secondo e il terzo pongono 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 William Gasarch, 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 affrontato la versione finita della prima delle scoperte 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 ottenere molte prestazioni dalle cose”, ha affermato James Glenn, informatico della Yale University. Nel 2008, Gasarch, Glenn e Clyde Kruskal dell’Università del Maryland hanno 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.