Congettura di Collatz

Istogramma per i numeri da 1 a 100 milioni

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].

Enunciazione del problema

La congettura riguarda il seguente algoritmo:

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

O, algebricamente:

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è:

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

Per esempio, iniziando con 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:

\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 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:

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.

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.
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.
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.
I numeri che rispettano la Congettura di Collatz sono infiniti. Quindi, non limitabili superiormente.
Se esiste un numero che non rispetta la Congettura di Collatz allora ne esistono infiniti che non la rispettano. Quindi non limitabili superiormente.
Possiamo sostituire "infiniti" a "molti" nei primi due punti.
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.
Esiste sicuramente un "loop" nel grafo dei numeri che rispettano la Congettura, quello formato dai numeri {4, 2, 1} (tre potenze di due, di cui una dispari). L'esistenza di un eventuale altro loop finito non comprendente i suddetti tre numeri implicherebbe necessariamente l'appartenenza ai numeri che non rispettano la Congettura. La ricerca di un tale loop finito equivale quindi alla ricerca di numeri che non rispettano la Congettura. Una tale ricerca potrebbe partire da un numero dispari incognito (diciamo x = 2n 1) definito come il più basso del loop (un numero pari non può costituire il minimo del loop in quanto seguirebbe una divisione per due) e da questo iniziare a salire con l'operazione (3x 1)/2 ed infine ridiscendere ad x con una divisione per 2 dopo aver raggiunto il valore 2x. Il loop si potrebbe tentare di costruire in modo (quasi) random utilizzando un numero finito di blocchi rappresentanti le due operazioni fondamentali, vale a dire la (3* 1)/2 e la */2. Lungo questa catena non si dovrebbe mai scendere al di sotto di x per non violare l'assunto iniziale. Ad esempio, dopo il primo blocco (3x 1)/2 deve seguire un altro blocco dello stesso tipo, altrimenti (con una divisione per due) si scenderebbe al di sotto di x. Se si dimostrasse l'impossibilità di costruire un tale loop la Congettura si rafforzerebbe notevolmente.
L'altra possibilità di falsificazione della Congettura è costituita da un divergenza all'infinito partendo da un valore dispari x rappresentante il minimo. Potrebbe anche essere vista come un loop infinito, dove la discesa sarebbe costituita dal valore x moltiplicato per potenze decrescenti di due. Difficile però immaginare una salita verso l'infinito ed individuare le caratteristiche necessarie che dovrebbe avere il valore x per rendere possibile una tale salita. Le salite più "ripide", almeno nella fase iniziale, si ottengono con valori di x = 2^n -1, vale a dire, ragionando su base binaria, con x costituito da bit tutti uguali ad 1. Ma non si può mettere n uguale all'infinito. Per cui, dopo una salita iniziale molto ripida si osserva un ritorno a comportamenti non sistematicamente divergenti.

Argomenti a favore

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

Evidenza sperimentale

La congettura è stata verificata (nel 2020) mediante computer per tutti i valori fino a $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à).

Considerazioni probabilistiche

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

Algoritmi per calcolare le sequenze di Collatz

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.

Ottimizzazioni

Se n è un multiplo di 4, può essere diviso per 4.

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

Più in generale, nella fattorizzazione prima di n è possibile sostituire la potenza di due con 2⁰=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 2⁰.

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 n è dispari, si può fare (3n 1) / 2, saltando un passaggio.

Motivo: se n è dispari, 3n è pure dispari (il prodotto di due numeri dispari è sempre dispari) e 3n 1 è pari, quindi può essere diviso per due.

Ad esempio: 3 × 35 1 = 106.

3m 1 fa sempre parte della successione di 4m 1. Quindi, se n ≡ 1 (mod 4), n può essere convertito in (n - 1) / 4 quante volte possibile, risparmiando un passaggio ogni volta. Il numero ottenuto, pari o dispari che sia, deve essere successivamente convertito in 3n 1.

Motivo: 4m 1 è sempre dispari, quindi diventerà 3(4m 1) 1 = 12m 4 = 4(3m 1), e può essere diviso per quattro.

Ad esempio: 405 può essere convertito come: 405 → 101 → 25 → 6 → 19. Anche la sequenza 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:

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}}

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}}

Nota storica sui vari nomi

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.

Nella cultura di massa

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.

Note

^ Brian Hayes, Computer Recreations. On the ups and downs of hailstone numbers, in Scientific American, gennaio 1984.
^ Gūnter M. Ziegler, Diamo i numeri? Orme Edizioni, 2011, p.116
^ On The 3x 1 Problem, su ericr.nl. URL consultato il 6 gennaio 2018.

Altri progetti

Wikimedia Commons contiene immagini o altri file sulla Congettura di Collatz

Collegamenti esterni

(EN) Eric W. Weisstein, Congettura di Collatz, 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

[1] Brian Hayes, Computer Recreations. On the ups and downs of hailstone numbers, in Scientific American, gennaio 1984.

[2] Gūnter M. Ziegler, Diamo i numeri? Orme Edizioni, 2011, p.116

[3] On The 3x 1 Problem, su ericr.nl. URL consultato il 6 gennaio 2018.

[1]

[2]

[3]

V · D · M Teoria dei numeri
Numeri più usati	Naturali · Interi · Pari e dispari
Principi generali	Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza
Successioni di interi	Fattoriale · Successione di Fibonacci · Numero di Catalan · Numero di Perrin · Numero di Eulero · Successione di Mian-Chowla · Successione di Thue-Morse
Caratteristiche dei numeri primi	Numero primo · Lemma di Euclide · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Test di primalità · Teorema fondamentale dell'aritmetica · Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Teorema dei numeri primi
Funzioni aritmetiche	Funzione moltiplicativa · Funzione additiva · Convoluzione di Dirichlet · Funzione φ di Eulero · Funzione di Möbius · Funzione tau sui positivi · Funzione sigma · Funzione di Liouville · Funzione di Mertens
Aritmetica modulare	Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Criteri di divisibilità · Teorema di Fermat sulle somme di due quadrati · Teorema di Wilson · Legge di reciprocità quadratica
Congetture	Congettura di Goldbach · Congettura di Polignac · Congettura abc · Congettura dei numeri primi gemelli · Congettura di Legendre · Nuova congettura di Mersenne · Congettura di Collatz · Ipotesi di Riemann
Altro	Problema di Waring
Principali teorici	Fibonacci · Fermat · Gauss · Eulero · Legendre · Riemann · Dirichlet
Discipline connesse	Teoria algebrica dei numeri · Teoria analitica dei numeri · Crittografia · Teoria computazionale dei numeri