Matematica: la congettura di Collatz

Congettura

Cos’è una congettura? È una proposizione che si presume vera ma non si è in grado di dimostrare rigorosamente. Le congetture affascinano perché funzionano per tutti i tentativi che si fanno per verificarla, cioè per trovare una dimostrazione di ciò che dicono. E questa loro non dimostrabilità le avvolge di mistero. Facciamo un piccolo recap.

Assiomi o postulati

Sono delle affermazioni così elementari che non possono essere dedotte da affermazioni ancora più semplici. A volte non sembrano molto elementari però si decide di arrestare il processo deduttivo perché non porterebbe più da nessuna parte se non girare il discorso utilizzando dei sinonimi. Ad esempio Assioma I della geometria euclidea:

Tra due punti qualsiasi è possibile tracciare una e una sola retta.

Qui si potrebbe obiettare “cos’è la retta? cos’è un punto? Il mio professore di Analisi I, Ezio Stagnaro, ci fece questo esempio:

Potete sostituire alla parola “punto” la parola “scarpe” e alla parola “retta” la parola “uomo” e verificare se detto così l’assioma funziona. Se poi riuscite a far funzionare l’analogia per tutti gli altri assiomi, vi accorgerete che punti e rette non sono oggetti in sé ma possono essere istanziati nella realtà in qualunque modo questo consenta di non pervenire a contraddizioni.

Proposizioni e teoremi

A partire dai fatti elementari (assiomi) costruiamo affermazioni più complesse (“La somma degli angoli interni di un triangolo è congruente con un angolo piatto” per rimanere nella Geometria Euclidea) che fanno discedere un fatto complesso (tesi) ad un certo numero finito di premesse (ipotesi). Il processo deduttivo che porta dalle ipotesi alla tesi senza saltare passaggi è detto dimostrazione del teorema. Se un teorema ha una dimostrazione l’affermazione è vera all’interno del sistema assiomatico e non può essere negata.

… e le congetture?

Se non riusciamo a trovare la dimostrazione siamo in una terra di mezzo. La proposizione è verificata in un numero più o meno grande di casi, sembra tenere, ma siccome non si possono provare tutti gli infiniti casi, non possiamo essere certi che funzioni sempre. Questa sicurezza ce la può dare solo una dimostrazione rigorosa.

Gli attacchi che i matematici sferrano verso queste proposizioni “maledette” a volte hanno qualcosa di epico, perché sono in grado di resistere per secoli all’assalto di menti sopraffine.

Per citarne un’altra di celebre, oltre a quella di Collatz, basti la congettura di Riemann, secondo la quale gli zeri non banali della funzione Zeta di Riemann hanno tutti parte reale uguale a 1/2. Anche di questa non si è ancora trovata una dimostrazione, benché fosse uno dei problemi inseriti da David Hilbert nell’elenco dei 23 problemi ancora da risolvere alla fine del XIX secolo (il problema numero 8, per la precisione).

Non è nemmeno provato che queste proposizioni non si possono dimostrare, almeno ci si metterebbe l’anima in pace. La proverbiale “pietra sopra” ad esempio è stata messa in un caso famoso: dopo secoli di tentativi da parte di matematici più o meno bravi di fornire una dimostrazione, si è trovato che l’assioma 5 della geometria euclidea – l’assioma delle parallele – non si poteva dimostrare come se fosse un teorema ma che anzi si poteva anche negare, addirittura in due modi, originando due nuovi sistemi indpendenti: le due geometrie non euclidee, quella di Riemann e quella di Bolyai/Lobacevskij.

In generale è stato dimostrato da Kurt Gödel che questo assioma è un punto debole come un punto debole ce l’ha qualsiasi altro sistema assiomatico (teoremi di incompletezza). Quindi in questo Gödel ha messo una pietra sopra sul fatto che in ogni sistema assiomatico ci sia un’affermazione che non può essere né dimostrata né negata all’interno dello stesso sistema.

Infatti si costruisce un altro sistema con una negazione del V postulato che ad esempio generi la geometria iperbolica e anche all’interno di questa non è dimostrabile né confutabile. Lo stesso vale per la geometria ellittica.

Non c’è niente da fare. Però questo teorema ha fatto finalmente in modo che la questione si potesse considerare chiusa una volta per sempre.

Ma in questo caso invece, come disse Paul Erdős, matematico ungherese, a proposito della congettura di Collatz

“La matematica non è ancora pronta per risolvere problemi del genere”

Paul Erdős

La congettura

La congettura di Collatz afferma che la successione così definita:

	x_{n+1} = 
	\begin{cases}
	3x_n + 1, & x_n \mod 2 = 0 \\
	x_n/2 & x_n \mod 2 = 1
	\end{cases}

converge sempre a 1 per n \ge N \in \mathbb{N} . Ricordo che x_n \mod 2 = 0 vuol dire che x_n è pari e x_n \mod 2 = 1 vuol dire che x_n è dispari.

Python: la libreria matplotib

Ora per divertirmi un po’ a vedere come funziona questa successione ho utilizzato Python e la libreria matplotlib che avevo già utilizzato per lo studio dell’apprendimento delle reti neurali.

È semplice installarla come libreria stand-alone per Python 3:

$ git clone git@github.com:matplotlib/matplotlib.git
$ cd matplotlib/
$ python3 setup.py install

Sorgente Python

Dopodiché la uso in un programma che semplicemente calcola la successione e la visualizza su un grafico

!/usr/bin/python3
import matplotlib.pyplot as plt

a = input("Dimmi un numero: ")
print("Successione di Collatz a partire da a=",a)
z = int(a)
s = []
s.append(z)

while (z != 1):
   print(z,", ")
   if (z % 2 == 0):
      z /= 2
   else:
      z = 3*z + 1
      
   s.append(z)
# la congettura d Collatz afferma che si esce sempre dal ciclo

# disegna
x = range(len(s))
plt.plot(x, s, label="Successione di Collatz")
plt.xlabel('iterazioni')
plt.ylabel('successione')
plt.title('Congettura di Collatz')
plt.legend() 
plt.grid(True)
plt.show()

Ci si può divertire a vedere il comportamento di questa succcessione che sembra davvero imprevedibile per numeri che non fanno parte della successsione delle potenze di 2. Ad esempio il 103 genera questo andamento