Sugli insiemi K della congettura di Collatz

Sugli insiemi K della congettura di Collatz

*

Michele Ventrone

Sunto - Dopo un’introduzione alla congettura di Collatz (problema del 3n+1), dimostro proposizioni e teoremi, costruisco e scompongo i nuovi insiemi K_t e K_t^*, ne determino il massimo e l’intersezione e propongo una congettura equivalente (partizionamento di N mediante gli insiemi K_t o K_t^*).

Parole chiave - Congettura di Collatz, problema di Syracuse, problema del 3n+1, convergenza, partizione, insiemi K_t e K_t^*.

Abstract - After a brief presentation of Collatz Conjecture (3n+1 problem), I will demonstrate propositions and theorems about new sets K_t e K_t^*; furthermore, I will determine their maximum and intersection and propose a conjecture equivalent (partition of N using sets K_t or K_t^*).

Key Words - Collatz conjecture, Syracuse problem, 3n+1 conjecture, convergence, partition, sets K_t and K_t^*.

§ 1. - Introduzione

La congettura - Venni a conoscenza della congettura di Collatz leggendo nell’estate 2004 un articolo divulgativo ([9]) dall’accattivante titolo: L’enigmatico pari e dispari che da cinquant’anni non fa dormire i matematici. Si parte da un intero positivo n, se è pari lo si divide per due, se è dispari lo si moltiplica per tre e vi si aggiunge uno, poi si ricomincia applicando le stesse regole sul numero ottenuto (v. §3). Ad esempio, partendo da 3 si genera la sequenza: 3 – 10 – 5 – 16 – 8 – 4 – 2 – 1.

L’altra forma dell’algoritmo del 3n+1 prevede, se n è dispari, il calcolo di (3n+1)/2 invece di 3n+1. Con 7 si ottiene la sequenza: 7 – 11 – 17 – 26 – 13 – 20 – 10 – 5 – 8 – 4 – 2 – 1.

Dopo qualche prova ci si accorge che le sequenze passano per uno: quelli che studiano la questione dicono che le traiettorie convergono. Si congettura che, da qualunque intero positivo si parta, le sequenze arrivino sempre tutte a uno in un numero finito di passi, ma nessuno lo ha ancora dimostrato.

Sul problema del 3n+1 si è creata una cospicua letteratura: purtroppo, quella squisitamente matematica che si può trovare sul Web, è in lingua inglese e in buona parte non immediatamente fruibile perché complessa. Il lettore potrà deliziarsi leggendo nella sezione “Paraphernalia Mathematica” di Rudi Mathematici ([2]) le idee singolari a cui fanno ricorso i matematici per attaccare il problema e alcuni dei “risultati” ottenuti.

Nella stessa sezione è enunciato il teorema di Terras, che dà buone speranze ma senza quantificare: “Quasi tutti i numeri hanno una Glide finita” e dove è spiegato che ciò equivale ad affermare che quasi tutti gli interi positivi generano sequenze che arrivano ad 1. Sull’argomento esistono congetture equivalenti, lemmi, teoremi, idee bizzarre e collegamenti con diversi settori della matematica da far venire il mal di testa. Si possono trovare altre notizie nei siti Web: [1], [2], [3], [4], [5], [6], [7], [8].

Il software di lavoro - Il mio passatempo estivo era diventato stimolante e, visti i nomi dei matematici che si erano interessati al problema, pensai che sarebbero passati altri cinquant’anni o più per venirne a capo ma, per motivi che non so spiegare, il problema m’incuriosiva molto.

Scrissi qualche programma di prova e a poco a poco, osservando il susseguirsi dei numeri e dei grafici sul monitor, iniziai a pormi parecchie domande. Durante le vacanze estive mi dedico alla programmazione dilettevole con maggiore frequenza e alla fine di luglio del 2005 realizzai un programma con più opzioni in Delphi 6.

Con il software speravo di evidenziare tendenze o regolarità delle sequenze. Quando formulavo nuove ipotesi, spesso, tralasciando l’approccio teorico, cercavo un primo conforto scrivendo nuovo codice che, girando, in quasi tutti i casi me le confutava senza pietà.

Ho preparato una versione ridotta del programma per i lettori di quest’articolo. Il software, selezionando una delle due forme dell’algoritmo di Collatz, determina il numero d’iterazioni necessarie alla convergenza a 1 di ogni intero positivo fino a 50.000.000, visualizza le sequenze, ne trova il massimo e può cercare tutti i numeri di un dato intervallo che convergono a 1 in un numero prefissato di passi.

Chi vuole potrà farmene richiesta via e-mail scrivendo nel campo “Oggetto” semplicemente “Syr”, entro un anno dalla pubblicazione di quest’articolo.

Struttura dell’articolo - I paragrafi dall’1 al 4 hanno un tono discorsivo, i seguenti, fino al paragrafo 11, contengono alcuni risultati dei quali quelli che, a mio avviso, potrebbero avere maggior rilievo sono: i teoremi 6.4 e 6.6 (uguaglianze notevoli), il teorema 8.2 (dei massimi di K_t e K_t^*) e il teorema 11.6 (intersezione degli insiemi K_t).

Nel §7 troverete degli esempi sulla costruzione di alcuni insiemi K. In una prima lettura di questo lavoro ci si potrà limitare ai risultati nei quali l’algoritmo è usato nella prima forma per poi passare, se si vuole, a quelli dell’altra forma mutatis mutandis.

Nell’appendice, infine, troverete la codifica di base dell’algoritmo in alcuni dei diversi linguaggi di programmazione che ho provato alla ricerca della possibilità di usare interi positivi molto grandi.

Gli insiemi K - Quando ero indotto ad indagare in una direzione, prendevo nota. Così, ipotesi dopo ipotesi, moltissime delle quali infruttuose, alcune osservazioni (v. inizio §6) mi spinsero a costruire gli insiemi caratteristici K_t e K_t^* (K_t o semplicemente K), a scomporli, a determinarne il massimo e l’intersezione e a formulare una congettura equivalente a quella di Collatz.

Gli insiemi K sono costituiti da interi positivi raggruppati secondo il numero di iterazioni che li portano a 1 con l’algoritmo di Collatz e forse partizionano N (congettura, v. §10).

Alcuni esempi - Nella Tabella 1 sono elencate le iterazioni necessarie per la convergenza a 1 dei primi 20 interi positivi e il massimo delle sequenze generate quando l’algoritmo è usato nella prima forma.

Tabella 1 – Iterazioni per arrivare a uno e massimi delle sequenze generate dai primi 20 interi positivi con l’algoritmo di Collatz nella prima forma.

1 Le sequenze entrano nel ciclo 4-2-1-4-2-1-… .

2 Esilarante in alcuni punti.

3 In [2] non è riportata la dimostrazione di questo teorema ma ne è fornita una traccia attraverso l’enunciato di lemmi.

4 Sia n un intero positivo. Applicando l’algoritmo di Collatz al numero n, si definisce Glide di n il numero t d’iterazioni necessarie per trovare nella sequenza, al posto t, il primo intero più piccolo di n e si scrive: Glide(n)=t. Altri chiamano la stessa cosa con “stopping time” (tempo di fermata) e scrivono σ(n)=t.

5 Nel settembre del 2006 quasi tutti i risultati di questo articolo, e altri che non ho incluso, erano già definiti, mentre lo studio dell’intersezione degli insiemi K (§10) risale al mese di marzo 2010 e quello sul massimo dei derivati dispari B (§9) al luglio 2010. Dal 2007 fino al 2010 ho dedicato pochissimo tempo a questo problema.

6 Il Free Pascal e Lazarus consentono di usare gli Int64 e i QWord (interi con segno e interi senza segno a 64 bit), il GNU Pascal ha i LongCard e i LongestCard (interi senza segno a 64 bit) e il Delphi6 gli Int64.

§ 2. - Origine del problema

L’origine del problema non è certa ma forse la si deve attribuire allo studente Lothar Collatz che lo propose negli anni trenta del secolo scorso mentre si interessava di grafi e funzioni in teoria dei numeri.

In seguito, negli anni 50 dello stesso secolo, H. Hasse, collega di Collatz, parlò del 3n+1 all’università di Syracuse e così il problema fu chiamato problema di “Syracuse” ([1], [6], [9]).

Il problema è conosciuto anche come congettura di Collatz, oppure: problema di Ulam, problema di Kakutani, algoritmo di Hasse, congettura di Twaites, dal nome dei matematici che riproponevano la questione contribuendo alla sua diffusione orale.

Con un sistema di calcolo distribuito oggi si cerca un controesempio, in altre parole, si tenta di individuare almeno un intero positivo che generi una sequenza che non passi per uno.

La congettura è stata verificata al computer per tutti gli interi n ≤ 19 × 2⁵⁸ ≈ 5.48 × 10¹⁸ (Oliveira e Silva, 2008), ma il controesempio non è stato trovato.

Sicuramente questo limite oggi sarà stato superato. Sul sito di Jeff Lagarias ([5], [6]) si legge di un’efficace e divertente voce che circolava negli anni 50 del secolo scorso negli ambienti matematici delle università degli Stati Uniti: si diceva che il problema facesse parte di una cospirazione tendente a rallentare la ricerca matematica negli USA.

Tra gli studiosi è diffusa l’opinione che la congettura potrebbe essere indimostrabile.

7 Alcuni riportano l’anno 1937, ad es. [3].

8 Città dello Stato di New York, Stati Uniti.

9 Il problema attrae molto alcuni matematici tanto che in Germania alla Katholische Universität Eichstätt si è tenuta, il 5 e 6 agosto del 1999, la prima conferenza internazionale sul problema di Collatz ([7]) e se ne è parlato anche all’Istituto Elie Cartan di Nancy (Francia) nel periodo 18-22 settembre del 2006. (Non ho trovato notizie di altre conferenze sulla congettura di Collatz.)

10 Nel 1931 Kurt Gödel ha dimostrato che l’aritmetica e tutte le teorie matematiche che la includono non sono complete, in altre parole: qualunque sia il gruppo di assiomi che si accetta, una Teoria coerente che includa l’aritmetica ha necessariamente almeno una proposizione che non può essere dimostrata o confutata a partire da quegli assiomi (Primo teorema d’incompletezza di Gödel).

Il famoso Paul Erdös osservò che la matematica non è pronta per risolvere questo tipo di problemi e offrì $500 per la dimostrazione. Anche altri offrirono denaro: H. S. M. Coxeter, $50 nel 1970, B. Thwaites, £1000 nel 1996 ([3], [5]). I matematici che lavorano sul problema ritengono che sia d’eccezionale difficoltà.

§ 3. - L’algoritmo di Collatz

Prima forma

Si parta da un intero positivo n e si applichino i seguenti passi:

1. Se n è pari lo si divida per 2;
2. Se n è dispari si calcoli 3n+1;
3. Con il numero ottenuto si riparta da 1).

Ossia, con n ∈ N₀ e i ∈ N₀, l’algoritmo è l’iterazione della funzione

T_i(n) = T_i−1(n)/2 se T_i−1(n) è pari;

T_i(n) = 3 · T_i−1(n) + 1 se T_i−1(n) è dispari. 3.1)

Con T₀(n)=n, se i=0.

Seconda forma

Si parta da un intero positivo n e si applichino i seguenti passi:

1. Se n è pari lo si divida per 2;
2. Se n è dispari si calcoli (3n+1)/2;
3. Con il numero ottenuto si riparta da 1*).

Ossia, con n ∈ N₀ e i ∈ N₀, l’algoritmo è l’iterazione della funzione

T_i^*(n) = T_i−1^*(n)/2 se T_i−1^*(n) è pari;

T_i^*(n) = (3 · T_i−1^*(n) + 1)/2 se T_i−1^*(n) è dispari. 3.2)

Con T₀^*(n)=n, se i=0.

§ 4. - Traiettorie

Nell’applicazione dell’algoritmo, partendo dall’intero positivo n, si genera una successione di interi che viene chiamata sequenza, traiettoria, orbita o volo di n ed è denotata con T(n) (o T^*(n), con la seconda forma dell’algoritmo).

Talvolta n è detto anche “seme” della traiettoria T(n). Il termine generico della traiettoria generata da n è denotato con T_i(n), con n fisso e con l’indice i variabile che indica l’i-esima iterazione, ossia la posizione del termine nella sequenza dopo i iterazioni. Se l’indice vale zero, allora si trova al posto zero nella sequenza: T₀(n)=n.

In mancanza di una dimostrazione della congettura si ipotizza che possano esistere tre tipi di traiettorie: quelle che contengono il numero 1 (convergenti), quelle che hanno infinito come massimo (divergenti), quelle che cadono in un ciclo diverso dal ciclo banale 4, 2, 1 (cicliche).

L’esistenza di traiettorie divergenti o cicliche non è stata ancora provata.

11 Con ciclo diverso dal ciclo 4,2,1.

12 L’esistenza di una traiettoria divergente o ciclica proverebbe che non tutti gli interi positivi passano per 1 e la congettura di Collatz risulterebbe falsa.

I termini del ciclo 4,2,1,4,2,1,… dopo il primo che si incontra, non si scrivono. Ad esempio, la traiettoria generata dal numero 21 nella prima forma è T(21)={21,64,32,16,8,4,2,1}.

Le traiettorie sono chiamate anche “Hailstone sequences” perché i numeri si comportano come i chicchi di grandine durante la caduta verso terra (T(n) o T^*(n)). Se la traiettoria generata da n converge, diremo semplicemente che converge.

Nel seguito denoteremo con TST l’insieme dei tempi di volo degli interi positivi convergenti, cioè l’insieme delle iterazioni necessarie alla convergenza degli interi positivi n.

Con la notazione V[n]=t indicheremo che n converge a 1 in t iterazioni, ovvero, con linguaggio suggestivo, che la durata del volo di n prima di fermarsi a terra è t. Per esempio V[3]=7 significherà che il volo di 3, misurato in termini d’iterazioni, è 7.

13 Da total stopping time, ossia “tempo totale di fermata” che è il numero di iterazioni necessarie per avere 1 a partire da n ed è denotato anche con σ(n).

Nel seguito, la locuzione “t-convergente” sarà equivalente a “convergente in t iterazioni” e la notazione abbreviata k_t indicherà che il numero k è t-convergente. Quest’ultima notazione mi è stata davvero utile nelle dimostrazioni.

14 σ(3)=7 equivale a V[3]=7.

Osservando le traiettorie e i loro grafici si nota che numeri diversi generano sequenze che da un certo punto in poi hanno gli stessi termini. Ad esempio, i numeri 142 e 143 generano la stessa sequenza dalla nona iterazione in poi con l’algoritmo nella prima forma, dalla sesta in poi con l’algoritmo nella seconda forma. Questa proprietà è chiamata coalescenza.

Figura 1 – Grafico della traiettoria del numero 142 (Algoritmo di Collatz nella prima forma).

Il grafico della traiettoria generata dal numero 142, applicando l’algoritmo di Collatz nella prima forma, è riportato nella Figura 1. L’ascissa indica il numero delle iterazioni e l’ordinata indica il valore ottenuto all’i-esima iterazione (o passo 1). La sequenza arriva a 1 in 103 iterazioni e il suo massimo è 9232.

Terminiamo questo paragrafo con due proprietà evidenti nelle due forme dell’algoritmo di Collatz.

Proprietà 4.1 - Se n converge allora ogni termine della sua traiettoria converge.

Ad esempio, tutti i numeri di T(3)={3-10-5-16-8-4-2-1} sono convergenti.

Se la congettura dovesse risultare falsa sarebbe vera anche la seguente proprietà.

Proprietà 4.2 - Se n non converge allora ogni termine della sua traiettoria non converge.

§ 5. - Costruzione degli insiemi K

Costruiremo, adesso, gli insiemi K legati alla congettura di Collatz e ne evidenzieremo le prime semplici proprietà.

Poniamo nello stesso insieme K_t la totalità degli interi positivi t-convergenti con l’algoritmo di Collatz nella prima forma:

K_t = {n ∈ N: n è t-convergente ∧ t ∈ N}. 5.1)

Ad esempio, applicando l’algoritmo nella prima forma:

• K₀ = {1}, perché 1 converge a 1 in zero iterazioni;
• K₁ = {2}, perché 2 converge a 1 in un’iterazione;
• K₂ = {4}, perché 4 converge a 1 in due iterazioni;
• K₇ = {20, 21, 128}, perché 3, 20, 21 e 128 convergono a 1 in sette iterazioni;
• Ecc., ecc.

Se l’algoritmo di Collatz è usato nella seconda forma, nella 5.1) aggiungeremo alla lettera K il simbolo asterisco *, ossia: