Matetango: Paul Erdős

Hailstone in inglese significa grandine e questa parola mi ha condotto a due eventi, uno legato agli abissi e uno alla matematica.
Stavo cercando immagini da correlare alla curiosità matematica della congettura di Collatz o "hailstone sequence", quando mi sono imbattuta in immagini stupende dei fondali marini, legati all' "operation hailstone".
Si tratta della Laguna di Truck (Truck Lagoon) e della sua flotta di relitti sommersi, conosciuta da tutti i subacquei come un posto paradisiaco.

Laguna di Truck - Relitto in superficie

La laguna si trova a circa 1000 km a sud est di Guam (U.S.A.), punto principale di approdo per le rotte intercontinentali.
Data la magnifica posizione strategica, durante la seconda guerra mondiale Truck diventò presto il baluardo dei Giapponesi nel Pacifico che, sentendosi al sicuro, concentrarono qui le loro maggiori flotte.
Tuttavia nelle notti tra il 16 e il 18 febbraio 1944, gli Stati Uniti sferzarono un attacco a sorpresa denominato appunto “Operazione Hailstone”, che distrusse e affondò oltre 45 mezzi tra navi militari, aerei, portaerei, un sommergibile, navi cisterna......insomma una Pearl Harbor al contrario avvenuta dopo quasi tre anni da quell'attacco giapponese del 7 dicembre 1941.
Nacque così la famosa “flotta fantasma di Truck” con relitti di navi che si trovano tra una profondità di +1 mt (di alcuni relitti fuoriesce il pennone dall’acqua) e i -200 mt.
Dopo 25 anni di bonifica e migliaia di immersioni per sminare completamente e rendere innocuo il pericoloso carico di queste navi da guerra, la laguna è divenuta parco, dove i relitti si sono ora completamente trasformati da tetri ricordi di una sanguinosa battaglia a una ricchissima colonia di coloratissimi pesci e coralli di ogni specie.
Un’esplosione di colori e coralli è assicurata visitando la Fujikawa Maru, una portaerei di 132 mt e 6938 tonnellate di stazza, mentre suggestiva è la visione della Sankisan Maru, una nave da carico di 112 mt di lunghezza e 4776 tonnellate di stazza, che giace su un fondale di circa 33 mt parzialmente in assetto di navigazione.
Troppo belle queste immagini per non condividerle in apertura di questo mio articolo, che dedicherò a una sorprendente sequenza matematica, anche lei correlata da altre altrettanto fascinose immagini.

Laguna di Truck - La Fujikawa Maru

Laguna di Truck - La Aikoku Maru

Laguna di Truck - Mitsubishi G4M Betty Bomber

Laguna di Truck - Un carro armato giapponese

Laguna di Truck - Bombardiere Mitsubishi Zero

Dopo queste sbalorditive immagini degli abissi legate alla "operation hailstone" , dedico questo articolo alla sequenza o congettura di Collatz nota appunto come "hailstone sequence" e a cui nessuno ha ancora dato una risposta e che può essere considerata un vero rompicapo della teoria dei numeri.
Nota anche come congettura di Ulam (da Stanisław Ulam) o di Thwaites (da Sir Bryan Thwaites), capita di incontrarla come algoritmo di Hasse (da Helmut Hasse) oppure come problema di Kakutani (da Shizuo Kakutani) o di Syracuse (il nome fu proposto da Hasse nel 1950, durante una visita alla Syracuse University), fu riproposta da Paul Erdős e prese anche il nome di "hailstone sequence" o "sequenza della grandine".
Tanti nomi diversi stanno a dimostrare il grande interesse per la questione, nata negli anni ’30 del secolo scorso ma diffusasi in campo matematico solo a partire dagli anni ’60.
Conosciuta anche come congettura 3n+1, è una congettura matematica che fu enunciata per la prima volta nel 1937 da Lothar Collatz, da cui prende il nome e riproposta, con un premio in denaro, da Paul Erdős.
Sebbene il matematico tedesco Lothar Collatz (6 luglio 1910 Arnsberg, Vestfalia, Germania - 26 settembre 1990 Varna, Bulgaria) abbia ricevuto molti onori per i suoi contributi, è ricordato forse solo per questa sua sequenza.
Al contrario il matematico ungherese Paul Erdős (26 marzo 1913 Budapest, Ungheria - 20 settembre 1996 Varsavia Polonia), che la ripropose, è ricordato come uno dei matematici più prolifici ed eccentrici della storia.

Lothar Collatz (a sinistra) e Paul Erdős

Erdős ha lavorato e risolto problemi legati alla teoria dei grafi, combinatoria, teoria dei numeri, analisi, teoria dell'approssimazione, teoria degli insiemi e probabilità......
Era una persona ossessionata dalla matematica, non desiderava soldi o fama e la maggior parte del denaro che riceveva per le conferenze lo donava per cause benefiche, tenendo per sé solo quanto era sufficiente a soddisfare il suo frugale stile di vita.
Dava soldi a tutti i mendicanti e si potrebbe dire che semplicemente non si curava affatto di ciò che non era matematica.
"Alcuni socialisti francesi hanno detto che la proprietà è un furto - diceva - Io penso che più che altro sia una seccatura."
Non aveva una casa e tutte le sue proprietà materiali erano stipate in due logore valigie che lo accompagnavano ovunque andasse.
"Another roof, another proof" era il suo motto" ("Un nuovo tetto, una nuova dimostrazione").
Ideò anche un vocabolario personale; spesso parlava del "Libro" riferendosi a un ipotetico libro, posseduto da Dio, nel quale erano racchiuse tutte le dimostrazioni sviluppate nella forma più elegante, "capo" indicava una donna, "schiavo" un uomo, "epsilon" un bambino (noto che epsilon, in matematica, indica una quantità piccola), "veleno" gli alcolici, "rumore" la musica, "predicare" il tenere una conferenza di matematica, e così via. Erdős utilizzava questo suo proprio gergo anche per indicare gli Stati; Samlandia erano gli Stati Uniti d'America (dalla figura dello Zio Sam), mentre Joseplandia era l'URSS (da Josif Stalin).
Per il suo epitaffio suggerì: "Végre nem butulok tovább" ("Adesso ho finito di diventare più stupido").
Tra le curiosità va ricordata la sua originale quanto inquietante idea di Dio, che negli anni '40 cominciò a chiamare SF, vale a dire "Sommo Fascista", immaginandolo infatti come una sorta di despota cosmico.
“Con tante brutte cose nel mondo - spiegava - non sono sicuro che Dio, ammesso che esista, sia buono”.
Insomma un genio davvero originale ed eccentrico, uno dei più prolifici matematici della storia (durante la sua vita ha scritto 1.485 articoli di matematica) e che, con i suoi studi, contribuì allo sviluppo della teoria di Ramsey e all'applicazione dei metodi probabilistici alla teoria stessa, da cui è nata una nuova branca dell'analisi combinatoria derivata in parte dalla teoria analitica dei numeri.
Durante la sua carriera, Erdős ha offerto premi in denaro per la soluzione di alcuni problemi irrisolti (Congetture di Erdős) e tra questi appunto la congettura di Collatz, per la quale Erdős offrì 500 dollari.

Congettura di Collatz

La congettura di Collatz è semplice da enunciare

e consiste nel definire una funzione f sugli interi positivi (numeri naturali):

f: N→N

f(n) = 3n + 1 se n è dispari

f(n) = n/2 se n è pari

Un intero n definisce una sequenza:

a(1) = n e, per i ≥ 1, a(i+1) = f(a(i))

Il problema consiste nel dimostrare che :

per ogni valore iniziale n, la sequenza a(i) raggiunge sempre 1.

Il problema rimane irrisolto, anche se la congettura è stata verificata per tutti i numeri n fino a n = 87x2^60 (nel 2017)
Più formalmente, le congetture in realtà sono due:

congettura debole di Collatz: nessun intero è divergente

congettura forte di Collatz: tutti gli interi positivi sono convergenti

Nelle successive sequenze vedremo che si passa da 1 per entrare in un ciclo (1, 4, 2, 1...) ma potrebbero esistere altri cicli che non contengono l’1.
In questo caso, risulterebbe vera la congettura debole ma non la forte, per ora appunto indimostrata.
Esiste solo una dimostrazione debole (molto importante peraltro) dovuta a Terras (vedi nota¹), che afferma (introducendo il concetto di stopping time) che la maggioranza degli interi positivi ha il comportamento che si conclude con il ciclo (1, 4, 2, 1.....).
Se proviamo infatti a costruire più sequenze a partire da un numero intero positivo, dividendolo per 2 se è pari, oppure moltiplicandolo per 3 e sommando 1 se è dispari, osserviamo che dopo un po’ di su e giù, la sequenza precipita incontrando numeri pari divisibili più volte per 2 e alla fine atterra su 1.

Proviamo alcuni numeri per vedere cosa succede:

n = 3; 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, ...
n = 4; 2, 1, 4, 2, 1, ...
n = 5; 16, 8, 4, 2, 1, 4, 2, 1, ...
n = 6; 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, ...
n = 7; 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1 ...
n = 11; 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1 ...
n = 156; 156, 78, 39, 118, 59, 178, 89, 268, 134, 67, 202, 101, 304, 152, 76, 38, 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1... (vedi grafico 1.1)
Come si vede la sequenza si ripete in un ciclo infinito: 4, 2, 1, 4, 2, 1 ...

Grafico 1.1

Analizzando queste sequenze scopriamo anche perché sia stata chiamata "hailstone sequence".
Il comportamento delle sequenze infatti ricorda la formazione della grandine causata da nuclei di ghiaccio portati su dalle correnti ascensionali e giù dal proprio peso, che si aggregano tra loro fino a diventare troppo pesanti e precipitare al suolo.
Da qui il nome di sequenza della grandine, in inglese "hailstone sequence".

Schema di formazione della grandine

Come si è detto, fino ad oggi la questione è ancora aperta ed in attesa di essere dimostrata vera o confutata.
Spinti dall’apparente semplicità della domanda, nel tempo molti matematici hanno provato a fornire una risposta rigorosa, ma il problema si è rivelato molto più ostico del previsto.
E una risposta alla domanda "Quanto ostico?" ce la fornisce proprio la valutazione del matematico ungherese Paul Erdős, che era solito offrire a colleghi e studenti una ricompensa economica per la soluzione dei problemi che proponeva.
Il premio partiva da pochi dollari per problemi che pur impegnavano duramente anche i più esperti e arrivò a 50$ per un problema ancora oggi irrisolto (frazioni egizie della congettura di Erdős-Strauss) , ma a chi avesse fornito un risposta alla congettura di Collatz , Erdős offrì ben 500 $.
Il suo intuito gli suggerì che forse servisse una matematica ancora da scoprire per risolvere la congettura.
Jeffrey Lagarias nel 2010 ha affermato a sua volta che "si tratta di un problema estremamente difficile, completamente fuori dalla portata della matematica attuale".
Quando negli anni ’60 il problema ritornò a interessare e cominciò a girare tra le università statunitensi, i calcolatori non erano ancora diffusi come oggi e il modo più comune per affrontare un problema come questo era ancora carta e penna.
L’apparente semplicità indusse molti a provarci, spendendo ore di calcoli senza però arrivare a una dimostrazione rigorosa.
Tanto che, ironicamente, qualcuno ipotizzò che la congettura facesse parte di una cospirazione sovietica, intesa a paralizzare la ricerca matematica statunitense.

Disposizione ad albero con radice in 1

Cerchiamo ora di individuare quali siano i punti da prendere in considerazione per riuscire a dimostrare o confutare la congettura di Collatz.
Dato che la congettura di Collatz suppone che per ogni valore iniziale n, la sequenza a(i) debba raggiungere sempre 1, a(i) potrebbe:
1) verificare tale ipotesi e precipitare a 1, dopo aver altalenato su e giù, terminando con il ciclo da 4 → 2 → 1 → 4 (…)
2) confutare tale ipotesi e terminare su un ciclo diverso da 4 → 2 → 1 → 4 (…)
3) confutare tale ipotesi e divergere, toccando numeri sempre maggiori e non terminando mai né a 1, né in un ciclo
Quindi la congettura può essere dimostrata vera o falsa, in base ad un rigoroso ragionamento logico-matematico (caso 1), oppure confutata trovando un controesempio (casi 2 o 3).
Si potrebbe confutare tale congettura solo trovando un numero di partenza che generi una sequenza che non contenga 1, che quindi converga a un ciclo di ripetizione che escluda 1 o che diverga.
Queste strade sono state attivamente esplorate da più di 50 anni, ma nessuna sequenza di questo tipo è stata trovata.
Non è stata trovata né una dimostrazione, né un controesempio.
Anche se la congettura non è stata dimostrata, la maggior parte dei matematici che hanno esaminato il problema pensano che la congettura sia vera perché le prove sperimentali e gli argomenti euristici lo sostengono.
Con l'ausilio del computer, è stato verificato ad oggi (2017) che tutti gli interi positivi fino a 87x2^60 (vedi nota²) terminano infatti, prima o poi, a 1.
Con l'aumento della velocità dei computer, verranno controllati valori sempre più alti, anche se è bene ricordare che questi test non potranno mai dimostrare la correttezza della congettura, ma solo l'eventuale falsità.

Ma quali strade sono state battute dai matematici, alla ricerca di regolarità, che diano la chiave di risoluzione?
Il primo passo è farsi un’idea di come varia la lunghezza della sequenza (numero dei passi), in base al numero di partenza.
Tenendo conto del numero da cui si parte, in alcuni casi il percorso è breve, mentre per altri è particolarmente lungo.
Ad esempio, partendo da n = 27 si arriva a 1 dopo un percorso di ben 111 passi, di cui 41 passi per i numeri dispari.
Nel suo viaggio la sequenza sale fino a 1.780, ridiscende a 167, si impenna fino a 9.232, per poi scendere più o meno a capofitto verso 1 (vedi grafico 1.2).

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 (...)

Grafico 1.2

Analizzando il numero dei passi è quindi evidente che anche un numero relativamente piccolo (come es n = 27) può avere tanti passi prima di arrivare a 1, come si vede dal grafico 1.2 ottenuto appunto utilizzando la funzione matematica della sequenza di Collatz.
Interessante anche notare la somiglianza notevole tra due grafici che si riferiscono alle sequenze che iniziano rispettivamente con n = 63.728.127 e n = 670.617.279 (vedi grafico 1.3 e 1.4)
E' stato verificato che n = 63.728.127 è il numero minore di 100 milioni con il tempo di arresto totale più lungo, con 949 passi, e n = 670.617.279 è il numero minore di 1 miliardo con il tempo di arresto totale più lungo, con 986 passi (vedi grafici 1.3 e 1.4).

Grafico 1.3

Grafico 1.4

Tenendo conto dei numeri di passi (per i numeri pari e dispari) si ottengono i grafici della congettura di Collatz e, se effettivamente tutte le sequenze portano a 1, allora gli interi positivi dovrebbero disporsi secondo un albero, con radice in 1.
Le diramazioni dovrebbero passare, prima o poi, per tutti i numeri interi positivi.
Anche se questo tipo di costruzione mostra delle regolarità, non ha fornito ad oggi lo spunto desiderato.
Per approfondire i più significativi tentativi di dimostrazione che si sono susseguiti lascio il link alla "Collatz conjecture"

Qui di seguito alcuni grafici della sequenza di Collatz che prendono in considerazione il numero di passi:

Grafico 1.5

Grafico 1.5 - lunghezza per i numeri dispari minori di 10.000 rispetto ai passi pari e dispari

Analizzando la lunghezza delle sequenze di Collatz per i numeri dispari minori di 10.000, si osservano frequenti gruppetti di numeri vicini che hanno la stessa lunghezza. Poiché due numeri dispari consecutivi non hanno fattori primi in comune, si tenderebbe a escludere un legame tra lunghezza della sequenza e fattori primi.

Grafico 1.6

Grafico 1.6 - lunghezza per i numeri pari minori di 10.000 rispetto ai passi pari

Analizzando la lunghezza delle sequenze di Collatz per i numeri pari minori di 10.000, che come visto è la lunghezza della sequenza che aggrega il passo 3n + 1 con il successivo dimezzamento, si nota che l’andamento è simile a quello del grafico 1.5.

Grafico 1.7

Grafico 1.7 - distribuzione delle lunghezze

Analizzando la distribuzione delle lunghezze per i numeri dispari minori di 10.000, si nota che la gobba che si forma intorno alla lunghezza di 120 è (purtroppo) fuorviante, e si livella analizzando più numeri.

Grafico 1.8

Grafico 1.8 - rapporto tra numero di passi pari e numero di passi dispari

Il grafico mostra l’andamento del rapporto p/d.

Si nota come il numero di passi pari e quello dei passi dispari siano correlati: se la sequenza arriva ad 1, i primi devono compensare in diminuzione l’effetto dei secondi in aumento.

Grafico 1.9

Grafico 1.9 - distribuzione del numero di passi pari e del numero di passi dispari

Evidenzia la distribuzione di passi pari e dispari

Grafico 1.10

Grafico 1.10 - stessa lunghezza per 943, 945, 947 e 949
Mette in evidenza un gruppo di numeri dispari consecutivi con la stessa lunghezza di sequenza: 943, 945, 947, 949. Si noti l’ampiezza del viaggio di 943 e come invece 949 proceda piatto.

Ottimizzando la f(n) = 3n + 1 con la relazione "shortcut" f(n) = (3n + 1)/2 e riformulando la congettura di Collatz in campo complesso, vale a dire passando dalla funzione "shortcut" di Collatz a una funzione olomorfa sull'intero piano di Gauss, si ottiene:

f(z)=1/4(4z+1−(2z+1)cos(πz))

e si ricava il suggestivo frattale di Collatz.

Frattale di Collatz

La procedura di Collatz può essere vista come l’iterazione della funzione, limitata ad argomenti interi.

Iterando la funzione, si trova che diverge per alcuni valori iniziali di z e converge per altri; colorando i punti del piano complesso in nero, se l’iterazione diverge utilizzando quel punto come valore iniziale e con colori differenti se converge, si ottiene il disegno, riportato nella figura (da Pokipsy76 – English wikipedia, Public Domain), che ricorda in vari particolari quello dell’insieme di Mandelbrot.

Concludendo l'"hailstone sequence" dimostra che parte della bellezza della matematica è data dal fatto che modelli apparentemente semplici portano a domande e teorie molto più complicate ed è l'esempio perfetto di un semplice problema che anche le più grandi menti matematiche del mondo non sono riuscite a risolvere.

Certo non sembra che in termini pratici o applicativi possa portare a nuove scoperte, ma certamente la sua risoluzione potrà essere forse solo determinata, come ipotizzava Erdős, applicando metodi e procedimenti matematici innovativi che oggi sono ancora sconosciuti.

Sorprendentemente il 3 ottobre 2017 Duccio Fanelli, docente del Dipartimento di Fisica e Astronomia dell’Università di Firenze e Timoteo Carletti, docente del Dipartimento di Matematica dell’Università di Namur in Belgio, hanno pubblicato, sul Bollettino dell'Unione Matematica Italiana, "Quantifying the degree of average contraction of Collatz orbits", un'analisi della congettura che si propone come tappa di avvicinamento verso la dimostrazione di quanto ipotizzato dal matematico tedesco.....riusciranno nell'impresa?

Note

¹Per chi volesse approfondire l'argomento suggerirei i seguenti siti

http://www.cecm.sfu.ca/organics/papers/lagarias/paper/html/node4.html

http://www.cecm.sfu.ca/organics/papers/lagarias/paper/html/paper.html

² Per visualizzare questo numero si tenga presente che 2^60 = 1.152.921.504.606.846.976 da moltiplicare ancora per 87

Fonti

From the book
La guerra del Pacifico 1941-1945 - Il più grande conflitto aeronavale della storia, di B. Millot - Rizzoli 2002

Iteration of the Number − Theoretic Function f(2n) = n, f(2n + 1) = 3n + 2 di C.J.Everet - Adv.Math (1977)

From website
https://en.wikipedia.org/wiki/Operation_Hailstone
https://en.wikipedia.org/wiki/Collatz_conjecture
http://www.unifimagazine.it/dimostrare-la-congettura-collatz/
From the pictures
http://scubatravel.se
http://www.perthscuba.com/galleries/truk-lagoon-micronesia/
http://www.watermanpolyhedron.com/Collatzconjecture.html
http://swimmingthestyx.com/?p=447
https://commons.wikimedia.org/w/index.php?curid=7188269
http://wikipedia.org (alcune immagini sono state rielaborate con PhatoShop)
From the video
Operation Hailstone
https://www.youtube.com/watch?v=kMgIrtq5M4o
Professor David Eisenbud Berkeley University - California
http://www.popularmechanics.com/technology/news/a22246/simple-problem-that-still-stumps-mathematicians/

Matetango

martedì 25 maggio 2021

Il "marziano" Paul Halmos, il matematico con la passione per i gatti e la fotografia

martedì 24 ottobre 2017

Hailstone...dagli abissi marini ai numeri