Sugli insiemi K della congettura di Collatz

N Iteraz. Max N Iteraz. Max

0 1 14 52

1 11

1 2 9 16

2 12

7 16 9 40

3 13

2 4 17 52

4 14

5 16 17 160

5 15

8 16 4 16

6 16

16 52 12 52

7 17

3 8 20 52

8 18

19 52 20 88

9 19

6 16 7 20

10 20

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.

§ 2. - ORIGINE DEL PROBLEMA

L’origine del problema non è certa ma forse la si deve attribuire allo studente

7 del secolo scorso mentre si

Lothar Collatz che lo propose negli anni trenta

interessava di grafi e funzioni in teoria dei numeri. In seguito, negli anni 50

dello stesso secolo, H. Hasse, collega di Collatz, parlò del all’università

3n+1

8

di Syracuse e così il problema fu chiamato problema di “Syracuse” ( ,

[1] [6],

). Il problema è conosciuto anche come congettura di Collatz, oppure:

[9]

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

≤ ≈

58

congettura è stata verificata al computer per tutti gli interi n 19x2

18 ( ), ma il controesempio non è stato trovato.

5.48x10 Oliveira e Silva 2008

Sicuramente questo limite oggi sarà stato superato. Sul sito di Jeff Lagarias

( , ) si legge di un’efficace e divertente voce che circolava negli anni 50

[5] [6]

del secolo scorso negli ambienti matematici delle università degli Stati Uniti:

si diceva che il problema facesse parte di una cospirazione tendente a

9

rallentare la ricerca matematica negli . Tra gli studiosi è diffusa

USA

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

Michele Ventrone – 8 maggio 2011 - 13 settembre 2011 – 22 gennaio 2012 4

10

l’opinione che la congettura potrebbe essere indimostrabile . Il famoso Paul

Erdös osservò che la matematica non è pronta per risolvere questo tipo di

per la dimostrazione. Anche altri offrirono denaro: H.

problemi e offrì $500

S. M. Coxeter, nel , B. Thwaites, nel . I

$50 1970 £1000 1996 ( )

[3],[5]

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

0 0

( )

 T n

−

 i 1 se T ( n ) è pari

( ) −

= i 1



T n 2 3.1)

i ( )

 ⋅ +

3 T n 1 se T ( n ) è dispari .

− −

i 1 i 1

con T (n)=n, se i=0.

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

0 0

( )

 *

T n *

i se T ( n ) è pari



 i

( ) 2

=

* 

T n ( ) 3.2)

i ⋅ +

*

 3 T n 1 *

i se T ( n ) è dispari .

 i

 2

*0

con T (n)=n, se i=0.

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

Michele Ventrone – 8 maggio 2011 - 13 settembre 2011 – 22 gennaio 2012 5

§ 4. - TRAIETTORIE positivo, si genera

Nell’applicazione dell’algoritmo, partendo dall’intero n

una successione di interi che viene chiamata sequenza, traiettoria, orbita o

*

volo di ed è denotata con (o ).

n T(n) T (n), con la seconda forma dell’algoritmo

Talvolta è detto anche “seme” della traiettoria . Il termine generico

n T(n)

della traiettoria generata da è denotato con , con fisso e con l’indice

n T (n) n

i

variabile che indica l’ iterazione, ossia la posizione del termine nella

i i-esima

. Se l’indice vale zero, allora si trova al posto zero

sequenza dopo n i T (n)=n

0

nella sequenza. In mancanza di una dimostrazione della congettura si

ipotizza che possano esistere tre tipi di traiettorie: quelle che contengono il

numero , quelle che hanno infinito come massimo ( ),

1 ( )

convergenti divergenti

, , ( ).

quelle che cadono in un ciclo diverso dal ciclo banale 4 2 1 cicliche

11 12

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

I termini del ciclo , dopo il primo che si incontra, non si

4,2,1,4,2,1,… 1 con l’algoritmo

scrivono. Ad esempio, la traiettoria generata dal numero 21

nella prima forma è . Le traiettorie sono chiamate

T(21)={21,64,32,16,8,4,2,1}

anche “Hailstone sequences“ perché i numeri si comportano come i chicchi

*

di grandine durante la caduta verso terra ( ). Se la traiettoria (o )

T(n) T (n)

[3]

converge, diremo semplicemente che converge. Nel seguito

generata da n n

13

denoteremo con l’insieme dei tempi di volo degli interi positivi

TST

convergenti, cioè l’insieme delle iterazioni necessarie alla convergenza degli

interi positivi . Con la notazione =t indicheremo che converge a in

n V[n] n 1

iterazioni, ovvero, con linguaggio suggestivo, che la durata del volo di

t n

14

prima di fermarsi a terra è . Per esempio significherà che il volo di

t V[3]=7

, misurato in termini d’iterazioni, è . Nel seguito, la locuzione ”

3 7 t-

” sarà equivalente a ” ” e la notazione

convergente in t iterazioni

convergente

abbreviata indicherà che il numero è . Quest’ultima

k k t-convergente

t

notazione mi è stata davvero utile nelle dimostrazioni. 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 e

142

generano la stessa sequenza dalla nona iterazione in poi con l’algoritmo

143

nella prima forma, dalla sesta in poi con l’algoritmo nella seconda forma.

Questa proprietà è chiamata coalescenza.

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.

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

∞

14 σ

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

∞

Michele Ventrone – 8 maggio 2011 - 13 settembre 2011 – 22 gennaio 2012 6

Figura 1 – Grafico della traiettoria del numero 142 (

Algoritmo di Collatz nella prima

).

forma

Il grafico della traiettoria generata dal numero applicando l’algoritmo di

142, . L’ascissa indica il

Collatz nella prima forma, è riportato nella Figura 1

numero delle iterazioni e l’ordinata indica il valore ottenuto all’i-esima

iterazione ( ). La sequenza arriva a in iterazioni e il suo massimo

o passo 1 103

.

è 9232

Terminiamo questo paragrafo con due proprietà evidenti nelle due forme

dell’algoritmo di Collatz.

PROPRIETÀ 4.1 - Se converge allora ogni termine della sua traiettoria

n

converge. { }

Ad esempio, tutti i numeri di sono convergenti.

T(3)= 3-10-5-16-8-4-2-1

Se la congettura dovesse risultare falsa sarebbe vera anche la seguente

proprietà.

PROPRIETÀ 4.2 - Se non converge allora ogni termine della sua

n

traiettoria non converge.

Michele Ventrone – 8 maggio 2011 - 13 settembre 2011 – 22 gennaio 2012 7

§5. – COSTRUZIONE DEGLI INSIEMI K

legati alla congettura di Collatz e ne

Costruiremo, adesso, gli insiemi K

evidenzieremo le prime semplici proprietà. Poniamo nello stesso insieme K

t

la totalità degli interi positivi con l’algoritmo di Collatz nella

t-convergenti

prima forma:

∈ ∧ ∈

K = {n N : n è t-convergente t N} . 5.1)

t o

Ad esempio, applicando l’algoritmo nella prima forma:

K = { }, perché converge a in zero iterazioni;

1 1 1

0

K = { }, perché converge a in un’iterazione;

2 2 1

1 = { }, perché converge a in due iterazioni;

K 4 4 1

2 … … …

K = { , , , }, perché , , e convergono a in sette

3 20 21 128 3 20 21 128 1

7

iterazioni;

ecc., ecc.

Se l’algoritmo di Collatz è usato nella seconda forma, nella 5.1)

*

aggiungeremo alla lettera K il simbolo asterisco , ossia:

∈ ∧ ∈

*t = {n N : n è t-convergente t N} . 5.2)

K o

Cominciamo con l’affermare, con la proposizione che segue, che gli insiemi

*t t

e contengono almeno il numero .

K K 2

t

PROPOSIZIONE 5.1 ( )

fondamentale

∀ ∈ *t

t N , K e K sono non vuoti.

t

DIMOSTRAZIONE ∈ 15

t

Banalmente: qualunque sia è , poiché applicando l’algoritmo di

t N V[2 ]=t t

Collatz (nella prima o nella seconda forma) si divide per due, volte.

2 t

*t t

vi è almeno .

Quindi in ■

K (K ) 2

t

Nel successivo paragrafo vedremo che gli insiemi , per , non

6 K t>4

t

contengono solo il numero .

2 ∈ t

Ad ogni si può associare per il tramite di e ad

OSSERVAZIONI - t N K 2

t ∈

t

ogni , il quale contiene almeno , si può associare , pertanto la

K 2 t N

t

15 t t 0

V[2 ]=t indica che 2 converge a 1 in t iterazioni. In particolare V[2 ]=0, cioè: 1 converge a 1 in 0

iterazioni.

Michele Ventrone – 8 maggio 2011 - 13 settembre 2011 – 22 gennaio 2012 8

{ }

collezione di insiemi è numerabile e . Ovviamente anche la

K TST=N

∈

t t N

{ }

*t

famiglia è numerabile.

K ∈

t N

Possiamo allora enunciare i seguenti corollari con l’algoritmo di Collatz

nelle due forme.

COROLLARIO 5.2 - Esiste sempre un tempo di volo.

{ } { }

*t

COROLLARIO 5.3 - Ognuna delle famiglie e è

K K

∈ ∈

t t N t N

numerabile. *t

E’ semplice mostrare che gli insiemi ( ) sono a due a due disgiunti.

K K

t

16

PROPOSIZIONE 5.4 ( Delle classi di N , algoritmo nella prima forma e

o

)

nella seconda forma

≠

Se t e t , con t t , sono nell’insieme TST, allora

1 2 1 2

∩ ∅

i) K K =

t1 t2

∩ ∅

* *t1 *t2

i ) K K = .

DIMOSTRAZIONE

i) - Algoritmo nella prima forma - Per la proposizione , e sono

5.1 K K

t1 t2

∩ ≠∅ ≠

non vuoti. Supponiamo per assurdo che , con .

K K t t

t1 t2 1 2

∈ ∩ 117

. Da e da segue poiché gli elementi

Sia k K K V[k]=t V[k]=t t =t

t1 t2 2 1 2

dell’intersezione devono convergere a con lo stesso numero di iterazioni,

1

≠ ∩ ∅

contro l’ipotesi che . Dunque .

t t K K = ◙

1 2 t1 t2

*

i ) - Algoritmo nella seconda forma – La dimostrazione è analoga alla

*

precedente: basta aggiungere l’asterisco agli insiemi . ■

K

t

∈

Un numero si trova solo in .

OSSERVAZIONI - k K (tale che V[k]=t) K

t t

∀ ∈

t

, , si trovano in un unico . Lo stesso

Ovviamente anche le potenze 2 t TST K

t

∈ *t

avviene per .

k K E’ naturale porre le seguenti domande. E’ possibile

QUESTIONI - { } { }

*t *t

determinare il massimo di ogni e di ogni ? Le famiglie e

K K K K

∈ ∈

t t t N t N

partizionano ? Risponderò alla prima nel . Nel ritroverete nei

N §8 §10

o

dettagli la seconda.

16 Non di equivalenza.

17 σ

V[k]=t equivale a (k)= t .

∞

1 1

Michele Ventrone – 8 maggio 2011 - 13 settembre 2011 – 22 gennaio 2012 9

§6. - SCOMPOSIZIONE DEGLI INSIEMI K

*t possono essere costruiti mediante ricerca bruta al

Gli insiemi K (K )

t *t-1

computer oppure attraverso gli elementi dell’insieme precedente .

K (K )

t-1

Ottenni la con l’aiuto del mio software.

Tabella 2 (alla fine di questo paragrafo)

Cercai gli interi di un determinato intervallo di interi positivi convergenti a 1

nello stesso numero di iterazioni. Esaminando la pensai alla

t Tabella 2

possibilità di costruire ogni a partire da con carta e penna, giacché

K K

t+1 t

contiene anche i doppi dei numeri dell’insieme precedente.

ogni K

t

Quando costruii la pensai che si potesse

Tabella 3 (alla fine di questo paragrafo)

fare la stessa cosa quando l’algoritmo è usato nella seconda forma. Dopo