sabato 21 marzo 2015

3n+1 parte 2 - Il frattale di Collatz

Gli insiemi numerici $\mathbb N$ e $\mathbb Z$ sono relativamente poveri dal punto di vista strutturale. Spesso, quindi, i problemi sui numeri interi vengono riformulati in ambito complesso, permettendo di mettere in campo l'"artiglieria pesante" della teoria delle funzioni. Non è difficile, ad esempio, ottenere dalla funzione di Collatz una funzione olomorfa sull'intero piano di Gauss. Partendo dalla sua versione abbreviata
$$ c(n)=
\begin{cases}
\frac{1}{2}n &\,, n \in 2\mathbb Z \\
\frac{1}{2}(3n+1) &\,, n \in 2\mathbb Z +1
\end{cases}
$$
tutto quello di cui necessitiamo sono due funzioni analitiche $f_1(z)$ e $f_2(z)$ che assumano i valori $1$ per $n$ pari e $0$ per $n$ dispari, e viceversa, ad esempio 
$$
f_1(z)=\cos^2\left(\frac{\pi}{2}z\right) \quad,\quad
f_2(z)=\sin^2\left(\frac{\pi}{2}z\right) \quad.
$$ Definiamo quindi
$$
c(z) = \frac{1}{2}z\cdot \cos^2\left(\frac{\pi}{2}z\right)
+ \frac{1}{2}(3z+1) \cdot \sin^2\left(\frac{\pi}{2}z\right) \; ; $$ con l'aiuto di un po' di goniometria calcoliamo
\begin{eqnarray*}
c(z) &=&
\frac{1}{2} \left( z\left(1-\sin^2\left(\frac{\pi}{2}z\right) \right)
+ (3z+1) \cdot \sin^2\left(\frac{\pi}{2}z\right)\right) \\
&=&
\frac{1}{2} \left(  z+ (2z+1)\sin^2\left(\frac{\pi}{2}z\right) \right) \\
&=&
 \frac{1}{2} \left(  z+ (2z+1)\cdot\frac{1}{2}(1-\cos(\pi z)) \right) \end{eqnarray*} ricavando infine
$$
c(z)= \frac{1}{4}\left( 4z+1-(2z+1)\cos(\pi z)\right) \quad.
$$
Studiando i valori di $z \in \mathbb C$ per cui l'iterazione successiva di tale funzione converge risp. diverge si ricava il suggestivo frattale di Collatz:



domenica 15 marzo 2015

Qualche lettura...

Non mi resta moltissimo tempo per leggere, purtroppo. In particolare, le mie nuove occupazioni mi rendono difficoltosa la lettura di testi impegnativi (di matematica "vera", ad esempio): riesco a leggere solo la sera, prima di addormentarmi, solitamente finché il libro mi cade di mano. Ma oltre a romanzi di Steinbeck, Child, Manzini, Grisham e Bartlett negli ultimi mesi sono riuscito a leggiucchiare anche qualche saggio non troppo lontano dalla matematica.
  • Innumeracy. Mathematical Illiteracy and its Consequences, di John Allen Paulos. Il titolo, sormontato da un neologismo traducibile forse con innumeratismo, ci dice già di che cosa si tratta: di una disquisizione sull'"illetteratismo matematico" e sulle sue conseguenze. L'autore si sofferma in particolare sulle possibili conseguenze dell'ignoranza dei principi più basilari del ragionamento logico, del calcolo mentale (quindi dell'incapacità di stimare) e del calcolo delle probabilità, che genera un substrato ideale per il diffondersi delle pseudoscienze (l'astrologia!) e ci rende vulnerabili alle truffe (Paulos cita lo stesso raggiro menzionato da Malvaldi nel suo ultimo romanzo).
  • Capra e calcoli. L'eterna lotta tra gli algoritmi e il caos,  di Marco Malvaldi (ancora lui) e Dino Leporini. Lasciati da parte per un momento i vecchietti del BarLume, il chimico Malvaldi, assieme al fisico Leporini (entrambi sono esperti in scienze computazionali), ci propone un viaggio attraverso la storia delle applicazioni del computer, mettendone ben in risalto i pregi e i difetti (questi ultimi dovuti essenzialmente all'eccessiva fiducia nella macchina, che spesso ci spinge ad utilizzarla in modo totalmente acritico), parlandoci di simulazioni, di realtà virtuale, di bolle immobiliari, e guarda un po', anche di filosofia. Leggetelo.
  • Contro il colonialismo digitale. Istruzioni per continuare a leggere. Come ha ribadito nel corso di una conferenza a cui ho assistito di recente, Roberto Casati (filosofo, direttore di ricerca al CNRS) non è contrario alle nuove tecnologie. Lo è, però, alle cattive applicazioni di queste ultime, come l'introduzione a tutti i costi dell'e-book in ambito didattico o l'uso a tutti i costi delle lavagne interattive, costose, poco pratiche e rapidamente obsolete (nella conferenza ha inoltre citato Spritz!: ricerca di ottimo livello, applicata però in modo discutibile). Interessante la sua posizione sui cosiddetti nativi digitali, che condivido pienamente: semplicemente, non esistono! Da leggere.
  • Sette brevi lezioni di fisica, di Carlo Rovelli. Ispirandosi ai Sei pezzi facili di Richard Feynman, il mio illustre quasi omonimo (Carlo è il mio secondo nome) condensa in poche, piccole pagine alcune grandi idee della fisica. Nessuna matematica (il libro è indirizzato a chi la fisica non la conosce), gradevole stile discorsivo (i contributi sono apparsi originariamente sul supplemento domenicale del Sole 24 Ore), il libro non può che rappresentare un invito ad approfondire (difatti sono già passato a Feynman).

sabato 7 marzo 2015

3n+1 parte 1 - Chicchi di grandine

Considera un numero naturale $n$. Se è pari, dimezzalo; se è dispari, triplicalo e aggiungi $1$. Ad esempio, con $n=13$ calcoliamo $13\cdot3+1=40$. Continua in questo modo: nel nostro caso, si otterrà $40:2=20$, poi $20:2=10$, e in seguito $5$ (che è dispari), e poi $3\cdot5+1=16$, e poi $8$, $4$, $2$, $1$, e in seguito il loop $4$, $2$, $1$ si ripeterà all'infinito.
Riproviamo partendo da 100: otteniamo 100, 50, 25, 76, 38, 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. Partendo da 27, invece, si ricava una sequenza molto più lunga: 27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1. Di nuovo, giungiamo al loop 4, 2, 1, 4, 2, 1, ...
Apparentemente, non esistono valori naturali iniziali che non conducono a 1: nessuna successione di questo tipo divergerà verso valori sempre più grandi, o presenterà comportamenti ciclici diversi da quello presentato. Si suppone pertanto che sia sempre così, ma nessuno lo ha ancora dimostrato: si tratta dell'enunciato della Congettura 3n+1, formulata dal matematico tedesco Lothar Collatz nel 1937, un problema aperto, piuttosto noto ma forse un po' "di nicchia" rispetto a congetture più celebrate. Esso riguarda il comportamento delle successioni $(a_i)$ ottenute a partire da un valore $a_0\in\mathbb N$ iterando la funzione
$$
c(n)=
\begin{cases}
3n+1 &,\,n\;\text{dispari} \\
\frac12 n &,\,n\;\text{pari} \end{cases} $$ 
Dal momento che per $n$ dispari $3n+1$ è sempre pari, a volte per proseguire più speditamente si preferisce porre direttamente $f(n)=\frac{3n+1}{2}$ per $n$ dispari.
A tali successioni viene spesso attribuito il suggestivo nome di hailstone sequences, siccome i loro termini sono soggetti a repentine ascese e discese, come i chicchi di grandine nella tempesta, come evidenziano ad esempio le rappresentazioni grafiche per $a_0=1000$:
 oppure per $a_0=1001$:
Ho sentito parlare per la prima volta della Congettura di Collatz (nota anche con altri nomi: Congettura di Ulam, Problema di Syracuse, Problema di Kakutani, ...) nell'ambito di un corso all'ETH, dove ci era stato chiesto di calcolarne i termini con l'aiuto di Mathematica (si tratta di un problema che pure io pongo, al Liceo, introducendo Maple o Excel). A colpirmi fu l'apparente semplicità della sua formulazione a fronte della sua difficoltà, un aspetto di molti problemi celebri che fu determinante nella mia scelta di orientarmi verso la teoria dei numeri.
La Congettura ammette una generalizzazione immediata all'insieme $\mathbb Z$. Qui, però, le cose si fanno un pochino più complicate: infatti sono stati identificati altri tre cicli possibili oltre a 1, 4, 2, 1. Il primo è breve: -1, -2, -1; il secondo è un po' meno breve: -5, -14, -7, -20, -10, -5; il terzo è decisamente più lungo: -17, -50, -25, -74, -37, -110, -55, -164, -82, -41, -122, -61, -182, -91, -272, -136, -68, -34, -17. Non se ne conoscono altri, e si congettura che non ve ne siano. 
Sulla Congettura di Collatz in rete si trova parecchio. Segnalo in particolare quattro lavori del matematico statunitense Jeffrey Lagarias: due papers introduttivi (qui e qui) e una imponente bibliografia ragionata in due parti (qui e qui).