Numero di Graham: il numero finito così grande che nessun cervello può immaginarlo

Se vi chiedessero qual è il numero più grande che la mente umana possa concepire, probabilmente direste "infinito". Ma infinito non è un numero, è un concetto. Tra i numeri finiti, invece, esiste un primato curioso che la matematica conserva con orgoglio: il numero di Graham, talmente immenso che l'universo osservabile non basterebbe a contenere la sua rappresentazione decimale, eppure così rigorosamente finito che ne conosciamo le ultime cifre.

L'aspetto più sorprendente è che il numero di Graham non è una stranezza inventata per impressionare. È nato come limite superiore alla soluzione di un problema concreto di teoria di Ramsey, una branca della matematica combinatoria che studia quando l'ordine emerge necessariamente dal caos. La storia parte da una stanza piena di amici e finisce in un ipercubo a dimensioni spaventose.

Il problema di Graham e Rothschild

Nel 1971 il matematico americano Ronald Graham e il collega Bruce Rothschild pubblicarono un risultato di teoria combinatoria di cui esiste un caso particolare facile da descrivere. Immaginate un ipercubo di dimensione n. Collegate ogni coppia di vertici con un segmento (in geometria si dice che si ottiene il grafo completo sui 2ⁿ vertici) e colorate ogni segmento di rosso o di blu, a vostro piacimento. Domanda: qual è il più piccolo n per cui, comunque scegliate la colorazione, esiste sempre un sottografo completo di 4 vertici complanari interamente monocromatico?

Graham dimostrò che la risposta esiste ed è finita. Mostrò un upper bound esplicito ma astronomico (oggi noto come "numero di Graham") e un lower bound molto piccolo: n ≥ 6. Il valore esatto della risposta resta sconosciuto. Ricerche successive hanno alzato il lower bound a n ≥ 13 e abbassato considerevolmente l'upper bound originale, ma il "numero di Graham" è entrato nella cultura matematica come simbolo dell'enormità che la combinatoria può produrre a partire da problemi quasi banali da enunciare.

Perché serve la notazione di Knuth

Per descrivere un numero così grande, le potenze non bastano. Una potenza come 3²⁷ si può ancora scrivere; una torre di potenze come 3³³³ già produce un numero con miliardi di miliardi di cifre. Per andare oltre, l'informatico Donald Knuth introdusse nel 1976 la notazione delle frecce in alto:

• 3 ↑ 3 = 3³ = 27
• 3 ↑↑ 3 = 3^(3³) = 3²⁷ ≈ 7,6 miliardi
• 3 ↑↑↑ 3 = 3 ↑↑ (3 ↑↑ 3) = una torre di potenze alta 7,6 miliardi di piani
• 3 ↑↑↑↑ 3 = un numero che già le mura della scrittura matematica fanno fatica a contenere

Ora definite g₁ = 3 ↑↑↑↑ 3. Poi g₂ = 3 ↑↑...↑↑ 3, dove il numero di frecce è esattamente g₁. Poi g₃, con un numero di frecce pari a g₂. E così via fino a g₆₄: questo è il numero di Graham, indicato di solito con la lettera G.

Per cogliere l'ordine di grandezza: g₁ già supera ogni cosa che la fisica conosca. Il numero di atomi nell'universo osservabile è circa 10⁸⁰. Il numero di Planck-volumi nell'universo è circa 10¹⁸⁵. Entrambi sono ridicolmente piccoli persino di fronte a g₁. E G richiede 63 ulteriori salti, ognuno dei quali fa esplodere il precedente.

Le ultime dieci cifre le conosciamo, le prime no

La cosa che lascia interdetti i non matematici è che, pur non potendolo "scrivere", si possono calcolare le sue ultime cifre. Le ultime dieci cifre del numero di Graham sono ...2464195387. Il motivo è che il calcolo del resto della divisione per potenze di 10 si stabilizza dopo poche iterazioni delle torri di potenze: una proprietà nota in teoria dei numeri come torre modulare. Le prime cifre, invece, restano irraggiungibili: nessun algoritmo che lavori sui simboli può ricostruire la rappresentazione decimale completa di G in tempi che abbiano senso fisico.

Martin Gardner, Scientific American e la fama

Il numero di Graham divenne celebre fuori dalla matematica nel novembre 1977, quando Martin Gardner gli dedicò la sua rubrica Mathematical Games su Scientific American. Gardner lo definì "il numero più grande mai usato in una dimostrazione matematica seria", entrando di diritto nel Guinness dei primati per i record matematici. Il record è stato superato da numeri come TREE(3), che nascono in teoria dei grafi e crescono ancora più rapidamente, ma G resta il simbolo più popolare di questa famiglia.

Cosa ci insegna G

Il numero di Graham ha un valore didattico oltre che storico. Mostra che la finitezza non implica trattabilità: un oggetto può essere "piccolo" rispetto all'infinito e, allo stesso tempo, totalmente impossibile da rappresentare con i mezzi del mondo fisico. Mostra anche che problemi posti in modo semplice ("colora i lati di un grafo") possono produrre risposte di cui non riusciamo a stabilire il valore esatto. E ricorda che le dimostrazioni matematiche, quando funzionano, lo fanno indipendentemente dalla nostra capacità di immaginare i numeri coinvolti: il bound di Graham è rigoroso, anche se nessuno potrà mai contare fino a G.

Per una trattazione tecnica completa, il lemma su Wolfram MathWorld e la voce su Wikipedia in inglese contengono tutti i passaggi formali. Per il piacere intellettuale, basta sapere che esiste là fuori un numero finito così grande da fare quasi rimpiangere l'infinito, che almeno è semplice da scrivere.