Visualizza wikitesto di Congettura di Collatz

[[File:CollatzStatistic100million.png|thumb|right|Istogramma per i numeri da 1 a 100 milioni]]
[[File:Collatz-stopping-time.svg|thumb|right]]

La '''congettura di Collatz''' (conosciuta anche come '''congettura 3''n'' + 1''', '''congettura di [[Syracuse (New York)|Syracuse]]''', '''congettura di [[Stanisław Ulam|Ulam]]''' o '''numeri hailstone'''<ref>{{cita news|url=https://www.jstor.org/stable/24969271|titolo=Computer Recreations. On the ups and downs of hailstone numbers|Brian Hayes|pubblicazione=[[Scientific American]]|data=gennaio 1984}}</ref>) è 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<ref>Gūnter M. Ziegler, ''Diamo i numeri?'' Orme Edizioni, 2011, p.116</ref>.

== Enunciazione del problema ==
La congettura riguarda il seguente [[algoritmo]]:

# Si prenda un [[numero intero|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:

:<math>f(n)=\begin{cases}
\frac{n}{2}, &\text{se }n\text{ pari,} \\ 
3n+1, &\text{se }n\text{ dispari.}
\end{cases} </math>

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

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

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:

:<math> \forall n \isin \mathbb{N} > 0 \ \exists i \isin \mathbb{N}: (a_0 = n \Rightarrow a_i = 1).</math>

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:

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

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 (grafo)|albero]], eccezion fatta per il [[ciclo (teoria dei grafi)|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 [[Numero naturale|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 [[Numeri pari e dispari|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 <math>2^{68}\approx 10^{20,5}</math>.<ref>{{Cita web|url=http://www.ericr.nl/wondrous/|titolo=On The 3x + 1 Problem|accesso=2018-01-06}}</ref> 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 [[algoritmo ricorsivo|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<sup>0</sup>=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<sup>0</sup>.
: ''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<sup>1</sup>×23), 23, 70 (2<sup>1</sup>×35), 35, 106 (2<sup>1</sup>×53), 53, 160 (2<sup>5</sup>×5), 5, 16 (2<sup>4</sup>), 1 (11 passi).

Se ''n'' è dispari, si può fare (3''n'' + 1) / 2, saltando un passaggio.  

: ''Motivo'': se ''n'' è dispari, 3''n'' è pure dispari (il prodotto di due numeri dispari è sempre dispari) e 3''n'' + 1 è pari, quindi può essere diviso per due.
: ''Ad esempio'': 3 × 35 + 1 = 106.

3''m'' + 1 fa sempre parte della successione di 4''m'' + 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 3''n'' + 1.
: ''Motivo'': 4''m'' + 1 è sempre dispari, quindi diventerà 3(4''m'' + 1) + 1 = 12''m'' + 4 = 4(3''m'' + 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:

:<math> f(n) = \begin{cases}
\frac{n}{4}, & \text{se } n \equiv 0 \pmod{4} \\
3 g(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}</math>

:<math> 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} </math>

== 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 ==
<references />

== Altri progetti ==
{{interprogetto|preposizione=sulla}}

== Collegamenti esterni ==
* {{Collegamenti esterni}}
* {{en}} Jeff Lagarias: ''[http://www.cecm.sfu.ca/organics/papers/lagarias/ The 3x + 1 problem and its generalizations]'', American Mathematical Monthly Volume 92, 1985, pp. 3 - 23.

{{Teoria dei numeri}}
{{Portale|matematica}}

[[Categoria:Teoria dei numeri]]
[[Categoria:Congetture matematiche|Collatz, congettura di]]