Congettura di Collatz 📖 Wikipedia

La congettura di Collatz (conosciuta anche come congettura 3n + 1, congettura di Syracuse, congettura di Ulam o numeri hailstone^[1]) è una congettura matematica tuttora irrisolta. Fu enunciata per la prima volta nel 1937 da Lothar Collatz, da cui prende il nome.

Paul Erdős disse, circa questa congettura, che «la matematica non è ancora matura per problemi di questo tipo», e offrì 500 dollari per la sua soluzione.^[2]

La congettura riguarda il seguente algoritmo:

1. Si prenda un intero positivo ${\displaystyle n}$.
2. Se ${\displaystyle n=1,}$ l'algoritmo termina.
3. Se ${\displaystyle n}$ è pari, si divida per due; altrimenti si moltiplichi per 3 e si aggiunga 1.

O, algebricamente:

${\displaystyle f(n)={\begin{cases}{\frac {n}{2}},&{\text{se }}n{\text{ pari,}}\\3n+1,&{\text{se }}n{\text{ dispari.}}\end{cases}}}$

È possibile formare una successione applicando la funzione ripetutamente prendendo come primo elemento un qualunque intero positivo e, ad ogni passaggio, applicare la funzione al risultato precedente, cioè:

${\displaystyle a_{i}={\begin{cases}n,&{\text{per }}i=0,\\f(a_{i-1}),&{\text{per }}i>0,\end{cases}}}$

Per esempio, iniziando con ${\displaystyle n=6,}$ otteniamo la successione 6, 3, 10, 5, 16, 8, 4, 2, 1.

La congettura di Collatz asserisce che questo algoritmo giunge sempre a termine, indipendentemente dal valore di partenza. Più formalmente:

${\displaystyle \forall n\in \mathbb {N} >0\ \exists i\in \mathbb {N} :(a_{0}=n\Rightarrow a_{i}=1).}$

La congettura risulterebbe quindi falsa se esistesse una successione che non contiene il numero 1; ciò potrebbe voler dire un ciclo che si ripete senza mai dare 1, oppure una successione illimitata superiormente.

A volte il problema è enunciato diversamente. La condizione di terminazione (cioè di fermarsi se ${\displaystyle n=1}$) viene rimossa dalla congettura, in modo che la sequenza non termini mai. Enunciando il problema in questo modo, la congettura di Collatz diventa l'affermazione che la successione generata dall'algoritmo raggiunga sempre il ciclo infinito 1, 4, 2, 1, 4, 2,...

Vi è un altro approccio per definire la congettura, approccio che considera di percorrere dal basso verso l'alto il grafo di Collatz. Tale grafo è definito da una "funzione inversa" di quella prima considerata:

${\displaystyle R(n)={\begin{cases}\left\{2n,{\frac {n-1}{3}}\right\},&{\text{se }}n\equiv 4{\pmod {6}},\\\{2n\},&{\text{altrimenti.}}\end{cases}}}$

Studiando il problema da questa prospettiva, il problema si definisce nel modo seguente. La congettura di Collatz si riduce alle due affermazioni:

• la funzione inversa forma un albero, eccezion fatta per il ciclo 1-2-4;
• tutti gli interi sono presenti nell'albero.

Alcune affermazioni certe (vale a dire dimostrabili) relative a questo problema, tenendo a mente il grafo orientato (infinito) che si ottiene ponendo come nodi i numeri naturali e come archi le relazioni (descritte sopra) che consentono di passare da un numero naturale al successivo.

1. Dato il carattere deterministico della relazione che determina il "successivo" di un numero, è unico il percorso uscente da ogni nodo, mentre sono "molti" i percorsi entranti in ogni nodo.
2. Tutti i nodi appartenenti all'unico percorso in uscita da un dato nodo o ai "molti" percorsi in entrata allo stesso nodo presentano il medesimo comportamento del nodo in esame; ossia, se il nodo in questione rispetta la congettura, allora tutti i nodi "collegati" la rispettano; se il nodo in questione non rispetta la congettura, allora nessuno dei nodi "collegati" la rispetta.
3. Fra i percorsi in entrata ad un qualsiasi nodo consideriamo in particolare il percorso "discendente" i cui nodi sono costituiti dal prodotto del numero rappresentato nel dato nodo per una qualsiasi potenza di due. Poiché le potenze di due sono infinite, risultano infiniti anche i nodi appartenenti a questo percorso "discendente". Questi infiniti nodi, per quanto detto al punto precedente, presentano il medesimo comportamento del nodo in esame. Da ciò discendono immediatamente i due punti seguenti.
4. I numeri che rispettano la congettura di Collatz sono infiniti. Quindi, non limitabili superiormente.
5. Se esiste un numero che non rispetta la congettura di Collatz allora ne esistono infiniti che non la rispettano. Quindi non limitabili superiormente.
6. Possiamo sostituire "infiniti" a "molti" nei primi due punti.
7. Gli eventuali infiniti numeri che non rispettano la congettura potrebbero costituire (anziché un insieme unico) più insiemi di cardinalità infinita disgiunti fra di loro. In tal caso i corrispondenti grafi infiniti risulterebbero non collegati fra di loro, oltre a non essere collegati al grafo dei numeri che rispettano la Congettura.
8. Esiste sicuramente un ciclo nel grafo dei numeri che rispettano la congettura, quello formato dai numeri ${\displaystyle \{4,2,1\}}$ (tre potenze di due, di cui una dispari). L'esistenza di un eventuale altro ciclo finito non comprendente i suddetti tre numeri implicherebbe necessariamente l'appartenenza ai numeri che non rispettano la congettura. La ricerca di un tale ciclo finito equivale quindi alla ricerca di numeri che non rispettano la congettura. Una tale ricerca potrebbe partire da un numero dispari incognito (diciamo ${\displaystyle x=2n+1}$) definito come il più basso del ciclo (un numero pari non può costituire il minimo del ciclo in quanto seguirebbe una divisione per due) e da questo iniziare a salire con l'operazione ${\displaystyle (3x+1)/2}$ ed infine ridiscendere a ${\displaystyle x}$ con una divisione per 2 dopo aver raggiunto il valore ${\displaystyle 2x.}$ Il ciclo si potrebbe tentare di costruire in modo (quasi) casuale utilizzando un numero finito di blocchi rappresentanti le due operazioni fondamentali, vale a dire ${\displaystyle (3n+1)/2}$ e ${\displaystyle n/2.}$ Lungo questa catena non si dovrebbe mai scendere al di sotto di ${\displaystyle x}$ per non violare l'assunto iniziale. Ad esempio, dopo il primo blocco ${\displaystyle (3x+1)/2}$ deve seguire un altro blocco dello stesso tipo, altrimenti (con una divisione per 2) si scenderebbe al di sotto di ${\displaystyle x.}$ Se si dimostrasse l'impossibilità di costruire un tale ciclo la congettura si rafforzerebbe notevolmente.
9. L'altra possibilità di falsificazione della congettura è costituita da un divergenza all'infinito partendo da un valore dispari ${\displaystyle x}$ rappresentante il minimo. Potrebbe anche essere vista come un ciclo infinito, dove la discesa sarebbe costituita dal valore ${\displaystyle x}$ moltiplicato per potenze decrescenti di 2. Difficile però immaginare una salita verso infinito ed individuare le caratteristiche necessarie che dovrebbe avere il valore ${\displaystyle x}$ per rendere possibile una tale salita. Le salite più "ripide", almeno nella fase iniziale, si ottengono con valori di ${\displaystyle x=2^{n}-1,}$ vale a dire, ragionando su base binaria, con ${\displaystyle x}$ costituito da bit tutti uguali ad 1. Ma non si può mettere ${\displaystyle n}$ uguale a infinito. Per cui, dopo una salita iniziale molto ripida si osserva un ritorno a comportamenti non sistematicamente divergenti.

Nonostante la congettura non sia stata dimostrata, la maggioranza dei matematici che se ne sono occupati pensa che la congettura sia vera. Vediamo alcuni motivi a supporto.

La congettura è stata verificata (nel 2020) mediante computer per tutti i valori fino a ${\displaystyle 2^{68}\approx 10^{20,5}}$.^[3] Intuitivamente, sarebbe sorprendente se il più piccolo controesempio fosse così grande da superare questo numero. Con l'aumento della velocità dei computer, verranno controllati valori sempre più alti (pur ricordando che questi test non potranno mai dimostrare la correttezza della congettura, ma solo l'eventuale falsità).

Se si considerano solo i numeri dispari della successione generata dall'algoritmo, si può affermare che in media il successivo numero dispari dovrebbe essere circa i 3/4 del precedente, fatto che suggerisce che essi, a lungo termine, decrescano fino a raggiungere 1.

Una specifica successione di Collatz può essere calcolata facilmente, come mostrato dal seguente esempio in pseudocodice:

function collatz(n)
  while n > 1
    if n dispari
      set n to 3n + 1
    else
      set n to n / 2

Oppure, sfruttando la ricorsione:

function collatz(n)
  if n > 1
    if n dispari
      collatz(3n + 1)
    else
      collatz(n / 2)

Questi programmi terminano quando la successione arriva a 1, per evitare di stampare un ciclo infinito di 4, 2, 1. Se la congettura di Collatz è vera, i programmi terminano sempre, qualunque sia l'intero positivo di partenza.

Se ${\displaystyle n}$ è un multiplo di 4, può essere diviso per 4.

Motivo: inizialmente è pari. Diviso per 2, è ancora pari, quindi può essere diviso per 2 una seconda volta.

Più in generale, nella fattorizzazione prima di ${\displaystyle n}$ è possibile sostituire la potenza di due con ${\displaystyle 2^{0}=1}$

Motivo: se la potenza di 2 nella fattorizzazione prima è maggiore di 0, allora il numero è pari, ed al punto successivo si avrà la stessa fattorizzazione con 2 elevato ad una potenza inferiore di uno. Ripetendo l'operazione, si arriva a ${\displaystyle 2^{0}=1}$

Ad esempio: invece di 15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1 (17 passi), si può calcolare 15, 46 (2¹×23), 23, 70 (2¹×35), 35, 106 (2¹×53), 53, 160 (2⁵×5), 5, 16 (2⁴), 1 (11 passi).

Se ${\displaystyle n}$ è dispari, si può fare ${\displaystyle (3n+1)/2,}$ saltando un passaggio.

Motivo: se ${\displaystyle n}$ è dispari, ${\displaystyle 3n}$ è pure dispari (il prodotto di due numeri dispari è sempre dispari) e ${\displaystyle 3n+1}$ è pari, quindi può essere diviso per 2.

Ad esempio: 3 × 35 + 1 = 106.

Il numero ${\displaystyle 3m+1}$ fa sempre parte della successione del numero ${\displaystyle 4m+1.}$ Quindi, se ${\displaystyle n\equiv 1{\pmod {4}},}$ allora ${\displaystyle n}$ può essere convertito in ${\displaystyle (n-1)/4}$ quante volte possibile, risparmiando un passaggio ogni volta. Il numero ottenuto, pari o dispari che sia, deve essere successivamente convertito in ${\displaystyle 3n+1.}$

Motivo: ${\displaystyle 4m+1}$ è sempre dispari, quindi diventerà ${\displaystyle 3(4m+1)+1=12m+4=4(3m+1),}$ e può essere diviso per 4.

Ad esempio: 405 può essere convertito come: 405 → 101 → 25 → 6 → 19. Anche la successione di Collatz normale contiene 19: 405 → 1216 → 608 → 304 → 152 → 76 → 38 → 19.

Quanto detto può essere usato per una nuova formulazione, equivalente alla precedente, della funzione di Collatz:

${\displaystyle f(n)={\begin{cases}{\frac {n}{4}},&{\text{se }}n\equiv 0{\pmod {4}}\\3g(n)+1,&{\text{se }}n\equiv 1{\pmod {4}}\\{\frac {n}{2}},&{\text{se }}n\equiv 2{\pmod {4}}\\{\frac {1}{2}}(3n+1),&{\text{se }}n\equiv 3{\pmod {4}},\end{cases}}}$

${\displaystyle g(n)={\begin{cases}n,&{\text{se }}n\not \equiv 1{\pmod {4}}\\g({\frac {n-1}{4}}),&{\text{se }}n\equiv 1{\pmod {4}}.\end{cases}}}$

All'inizio degli anni 1930, Lothar Collatz, uno studente dell'università di Amburgo, si occupava della teoria dei numeri e della teoria dei grafi. Partiva da un numero intero positivo, gli applicava un algoritmo iterativo, tracciava i grafi associati e si poneva domande ancora senza risposta.

Il matematico tedesco Helmut Hasse, amico di Collatz, diffuse il problema, noto anche con il nome algoritmo di Hasse o problema 3x+1. Poiché Hasse presentò il problema negli anni '50 durante una visita all'università di Syracuse (vicino a New York), propose di battezzarlo problema di Syracuse.

Il matematico polacco Stanisław Ulam fece circolare l'algoritmo al Los Alamos National Laboratory, dove lavorava durante la seconda guerra mondiale. Per questo il problema è anche noto con il nome problema di Ulam.

Negli anni '60 Shizuo Kakutani si interessò nuovamente al problema, anche chiamato problema di Kakutani.

La congettura di Collatz è citata:

• nel film La donna che canta da Jeanne Marwan durante una lezione di Matematica in Università;
• nel romanzo L'ultimo teorema di Arthur C. Clarke.
• Nella serie tv Iris affair dalla protagonista Iris che in un dialogo dice che il computer quantistico di nome Charlie oltre ad altre scoperte e soluzioni avrebbe risolto la congettura.

• Wikimedia Commons contiene immagini o altri file sulla congettura di Collatz

• Collatz, congettura di, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• (EN) Eric W. Weisstein, Collatz Problem, su MathWorld, Wolfram Research.
• (EN) Jeff Lagarias: The 3x + 1 problem and its generalizations, American Mathematical Monthly Volume 92, 1985, pp. 3 - 23.

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica