Congettura di Collatz

Sfogliando la rivista Quantamagazine.org, mi sono imbattuto in un recente articolo su un problema ancora in attesa di risoluzione: la Congettura di Collatz.
Ne avevo già scritto in precedenza, e rimando a quell’articolo per maggiori dettagli. Qui vale però la pena di ricordare la semplicità con cui si enuncia la congettura di Collatz e l’estrema difficoltà nella ricerca di una risposta definitiva, ricerca tuttora infruttuosa.
L’articolo di Quantamagazine.org racconta come, alcuni mesi fa, il matematico Terence Tao, pur senza risolvere la congettura, ha mosso un significativo passo in avanti.


La Congettura di Collatz

Rimando all’articolo citato per una descrizione completa. In breve, negli anni ’30 del ‘900, il matematico tedesco Lothar Collatz notò un curioso comportamento della sequenza di numeri interi positivi Ni costruiti, a partire da un numero N0, con le seguenti regole:

Il successore di Ni è:
3Ni + 1, se Ni è dispari
Ni/2, se Ni è pari.

Ebbene, provando con diversi numeri, si trova che, presto o tardi, la sequenza finisce nel loop:

4  –>  2  –>  1 –> 4 –> 2 …

Esempio:

17 –>  52  –> 26  –> 13  –> 40 –> 20  –> 10 –> 5 –> 16  –> 8  –> 4  –>  2  –>  1 –> 4 –> 2 …

Collatz congetturò che questo comportamento si presenti qualunque sia il numero intero positivo di partenza.


Un semplicissimo generatore di sequenze di Collatz si può realizzare con il solito Excel o LibreOffice Calc.
Scriviamo nella cella A1 il numero di partenza, ad esempio 13. Nella cella A2 scriviamo la formula:

=SE(RESTO(A1;2)=0;A1/2;3*A1+1)

e poi copiamo in basso la formula, finché non vediamo comparire il loop 4, 2, 1.

Adesso proviamo con 27 come valore iniziale in A1. Bisognerà allungare la serie, e non di poco!


I tentativi di dimostrazione

Questo tipo di problema viene in genere attaccato in due modi (come si è visto anche nell’articolo precedente, sulla ricerca di eventuali numeri perfetti dispari):

  • si cerca un eventuale contro-esempio; per la Congettura di Collatz basterebbe trovare un loop di numeri diverso dal 4  –>  2  –>  1  –>  4, oppure dimostrare che, a partire da un particolare numero, la sequenza continui mediamente a crescere indefinitamente;
  • si cerca di dimostrare che la congettura è vera.

Lo stato della ricerca

Ad oggi è stato verificato che tutti i numeri fino a 268 (pari a oltre 100.000.000.000.000.000.000) soddisfano la congettura. Ma questo, naturalmente, non dimostra nulla in modo definitivo.
Lo stato, invece, della dimostrazione rigorosa si trova nell’articolo di Quantamagazine.org (The Simple Math Problem We Still Can’t Solve).

Nel 1976 il matematico Riho Terras dimostrò che, per quasi tutti i numeri interi positivi, dopo l’applicazione di un numero opportuno di passi la sequenza raggiunge un valore minore di quello di partenza.
Cosa vuol dire quel quasi tutti? Vuol dire che è possibile verificare la cosa per una porzione dei numeri interi positivi, poi per una porzione dei rimanenti, poi per una porzione di quelli ancora rimasti, e così via. La frazione dei numeri ancora da esplorare si riduce progressivamente, senza però annullarsi mai.

Esempio:

  1. per i numeri pari basta un passo:  2n –> n (e metà dei numeri è andata);
  2. ci vogliono 3 passi, invece, per i numeri della forma 4n+1: 4n+1 –> 12n+4  –> 6n+2  –>  3n+1 (e metà dei rimanenti è andata);
  3. per i numeri della forma 16n+3 servono 6 passi: 16n+3  –> 48n+10  –> 24n+5  –> 72n+16  –> 36n+8  –> 18n+4  –> 9n+2 (i numeri di questa forma rappresentano un ottavo dei rimanenti).

Una strada più recente e promettente

L’anno scorso il matematico Terence Tao ha dimostrato che in realtà, sempre per quasi tutti i numeri, la sequenza raggiunge, prima o poi, un valore molto più basso, come N/2, o anche la radice quadrata di N, o il logaritmo di N, o una qualunque funzione f(N) che tenda all’infinito con N, non importa quanto lentamente.

Pur non essendo una dimostrazione, il risultato raggiunto da Tao aumenta la convinzione che la congettura sia vera, anche se è lo stesso matematico a riconoscere che, se e quando si troverà la soluzione, questo avverrà lungo una strada diversa.


Per chi fosse interessato ad approfondire il lavoro di Terence Tao, riporto due link: uno a una versione discorsiva del suo metodo (più digeribile) e uno alla descrizione più formale, per la quale serve un’attrezzatura matematica che, ahimè, non ho.

Foto di apertura di Pexels da Pixabay.

Ti è piaciuto? Condividilo!

Scritto da:

Pasquale

Mi chiamo Pasquale Petrosino, radici campane, da un paio d'anni sulle rive del lago di Lecco, dopo moltissimi anni vissuti a Ivrea.
Ho attraversato 40 anni di tecnologia informatica, da quando progettavo hardware maneggiando i primi microprocessori, la memoria si misurava in kByte, e Ethernet era una novità fresca fresca, fino alla comparsa ed esplosione di Internet.
Tre passioni: la Tecnologia, la Matematica per diletto e le mie tre donne: la piccola Luna, Orsella e Valentina.
Potete contattarmi scrivendo a: p.petrosino@inchiostrovirtuale.it