Numeri che fanno girare la testa

Oggi xkcd ha pubblicato una vignetta riguardante la congettura di Collatz. Si tratta di un giochino che funziona in questo modo: si prende un numero intero positivo qualunque, se è pari lo si divide per 2, se invece è dispari lo si moltiplica per 3 e si aggiunge 1. E si continua così, fino a che non si arriva a 1 (se si riesce ad arrivare a 1 e si vuole continuare col gioco, si entra in un ciclo: il numero successivo a 1 è 4, poi si ha 2, e di nuovo 1).

Qua a sinistra si può vedere un albero che rappresenta l'evoluzione di alcuni numeri. Come si vede, tutti finiscono a 1. La congettura di Collatz afferma che, comunque noi scegliamo un numero positivo, prima o poi arriviamo sempre a 1. È un giochino che si può fare con carta e penna, durante una riunione noiosa, per esempio. La vignetta suggerisce che se uno comincia a giocarci, poi non finisce più.

Ecco, una persona normale magari alla fine della riunione smette di calcolare e va a casa, ma un matematico forse no.

In effetti questo problema è stato studiato molto, e per molto tempo. È stato proposto nel 1937; nel 1972 Conway ha dimostrato che una generalizzazione della congettura è indecidibile (e qui potrebbero cominciare i guai: se fosse indecidibile anche la congettura, sarebbe inutile cercare una dimostrazione); in seguito ha dimostrato che non possono esistere cicli composti da meno di 400 termini (se esistesse anche solo un ciclo, di qualunque dimensione, la congettura sarebbe falsa, perché gli elementi del ciclo non arriverebbero mai a 1); nel 1985 Lagarias ha dimostrato che non possono esistere cicli di lunghezza minore di 275000, e a questo punto uno potrebbe anche dire “vabbè, dai, allora basta”.

Il fatto è che un matematico non si può accontentare di una serie di conferme alla sua teoria: un matematico vuole la dimostrazione.

La vuole trovare nonostante il parere autorevole di Paul Erdős, che nel 1985 ha affermato che la matematica non è ancora pronta per affrontare problemi così difficili.

Nel frattempo, mentre i matematici sviluppano nuove teorie per affrontare questo difficile problema, i calcolatori continuano a macinare numeri per analizzare sempre più in profondità l'albero di Collatz. Il primo grosso tentativo di studiare la congettura è partito nell'agosto del 1996, quando è stato lanciato un programma scritto in C su due workstation DEC Alpha a 133MHz e altre due a 266MHz. Il programma ha completato l'esame dell'evoluzione di tutti i numeri interi fino a 100·2⁵⁰ nell'aprile del 2000 (no, non ho sbagliato a scrivere).

L'algoritmo è stato migliorato e il programma è stato fatto ripartire nel giugno del 2004. Dopo 81.1 anni di cpu (suddivisi su più macchine, naturalmente), nel gennaio 2009 è stato fermato nuovamente: questa volta ha raggiunto il numero 20·2⁵⁸ (cioè 5764607523034234880), senza trovare alcun controesempio alla congettura — ah, dimenticavo: per maggior sicurezza ogni numero è stato controllato due volte. Un secondo gruppo di ricerca ha ottenuto, in maniera indipendente, lo stesso risultato.

Infine, nel 2001 è partito un progetto di calcolo distribuito che, ad oggi, ha superato la cifra 9·2⁵³.

Tutte queste prove non sono riuscite a trovare nessun controesempio alla congettura. Allora perché continuare? Sembra impossibile che la congettura, vera per così tanti numeri, possa dimostrarsi falsa per numeri ancora più grandi.

Eppure, questa non è una dimostrazione, e la storia della matematica ci insegna che già in altri casi sono stati trovati controesempi per numeri giganteschi. Ad esempio, la congettura di Pólya afferma che la maggior parte (cioè una parte superiore al 50%) dei numeri naturali minori di un dato numero ha un numero dispari di fattori primi. Nel 1958 si è dimostrato che la congettura è falsa, fornendo come controesempio un valore pari circa a 1.845·10³⁶¹. In seguito questo valore è stato abbassato fino a 906150257.

La congettura di Mertens, il cui enunciato riguardante le proprietà di un certo numero n è un po' troppo complicato per stare su questo margine, è stata confutata utilizzando un valore pari a e^3.21·1064. Nel 2006 questo limite è stato un po' abbassato, ed ora è pari a e^1.59·1040.

Esiste poi una proprietà riguardante i numeri primi, che afferma che a un certo punto il numero di numeri primi minori di un certo numero x supera il valore del logaritmo integrale di x. Nel 1914 è stato dimostrato che questo numero esiste. Nel 1933 è stato dimostrato che, se l'ipotesi di Riemann è vera, allora questo numero è maggiore di e^ee79. Nel 1955 è stato dimostrato che, senza la necessità di utilizzare l'ipotesi di Riemann, questo numero è minore di 10^1010963. In seguito questi valori sono stati abbassati, ma rimangono comunque enormi.

Enormi, ma anche piccoli, se confrontati con il numero di Graham: un numero talmente grande che non potrebbe essere contenuto all'interno dell'universo conosciuto, supponendo di poter memorizzare ogni sua cifra in uno spazio pari a un volume di Planck, pari a 4.22419·10⁻¹⁰⁵ metri cubi. Un numero usato in un dimostrazione, eh.

Uh, dimenticavo: come per tutti i grandi teoremi che si rispettino, esiste un premio di mille sterline destinato al primo che riesce a dimostrare, o confutare, la congettura di Collatz.

E, come succede per tutti i grandi teoremi che si rispettino, anche la congettura di Collatz non serve a niente.