Roberto A. Foglietta en Scienziati e ricercatori, Economists and Finance, IT - Information Technology ◽Freelance Consultant • ◾www.roberto.foglietta.name 8/3/2018 · 10 min de lectura · +500

La congettura di Collatz

La congettura di CollatzPublished on February 27, 2018 on Google Groups

Introduzione

La congettura di Collatz (o Congettura 3n+1), proposta da Lothar Collatz nel 1937, è uno dei più famosi problemi aperti in matematica e può essere enunciata in modo straordinariamente semplice come segue.

Si parta da un qualsiasi intero positivo a0=n; dopodiché, se esso è pari si definisca a1=n/2 mentre se è dispari si definisca a1=3n+1. Si applichi poi lo stesso procedimento ad a1 ottenendo a2 e così via.

La congettura afferma che, qualsiasi sia l'intero n da cui si parte, la successione definita per ricorrenza in tal modo raggiunge l'intero 1 dopo un numero finito di passi.

Ad esempio, partendo da n=12 si ha

  • 12, 6, 3, 10, 5, 16, 8, 4, 2, 1.

mentre partendo da n=17 si ha

  • 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

Partendo da n=27 sono necessarie ben 111 iterazioni, e la successione ricorsiva raggiunge 9232 prima di scendere fino ad 1:

  • 27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 21, 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.

In generale, il numero di iterazioni necessarie affinché partendo dall'intero positivo n si raggiunga 1 viene chiamato il tempo d'arresto di n.

Pertanto la congettura può essere riformulata dicendo che ogni intero positivo ha un tempo d'arresto finito. I tempi d'arresto dei primi numeri naturali sono i seguenti:

  • 0, 1, 7, 2, 5, 8, 16, 3, 19, 6, 14, 9, 9, 17, 17, 4, 12, 20, 20, 7, 7, 15, 15, 10, 23, 10, 111, 18, 18, 18, 106, 5, 26, 13, 13, 21, 21, 21, 34, 8, 109, 8, 29, 16, 16, 16, 104, 11, 24, 24, ... (questa è la successione A006577 nel database OEIS).

Nonostante essa possa essere facilmente spiegata a qualsiasi bambino delle scuole elementari, la congettura di Collatz risulta essere un problema straordinariamente arduo, tant'è che lo stesso affermò che «la Matematica attuale, semplicemente, non è ancora pronta per esso».

Questo però accadeva negli anni '40 ma da allora la congettura di Collatz è stata studiata da molti matematici anche con il supporto dei calcolatori moderni. Perciò da allora sono stati fatti molti passi in avanti nel comprendere l'intima natura della congettura di Collatz sebbene ancora nel 2010, Jeffrey Lagarias ribadì l'opinione di Paul Erdős.

Le verifiche sperimentali con l'uso del calcolatore mostrano che essa è vera fino a n=86x2^70; ovviamente, questo non basta per dedurre che essa è vera per ogni valore di n, dato che potrebbe esistere un controesempio il cui ordine di grandezza è inaccessibile agli attuali metodi computazionali.

Un intero n potrebbe fornire un controesempio alla congettura di Collatz in due circostanze: o se la successione per ricorrenza definita a partire da n diverge all'infinito, oppure se essa entra in un ciclo diverso dal ciclo banale (4, 2, 1).

Come detto, al momento non si sa se ciò possa accadere tuttavia, grazie al lavoro di vari autori (Steiner, Simons, de Weger, etc.) è stato possibile escludere rigorosamente l'esistenza di cicli non banali di lunghezza fino a 68.

Inoltre, si sa che per "molti" interi positivi l'iterazione effettivamente termina ad 1. Più precisamente, Krasikov e Lagarias hanno dimostrato nel 2003 che il numero di interi nell'intervallo [1, x] aventi tempo d'arresto finito è almeno proporzionale a x^{0.84}.

–Fonte: Wikipedia Italia e Wikipedia Inglese

Condizioni di convergenza delle serie di Collatz

Se n è dispari allora 3n+1 ma n=(m+1) perché altrimenti n=1. Quindi m è pari, inoltre

  • 3m+3+1 = 3m+4 con m≥1.

Quindi 3m+4 è pari ma questo già lo si sapeva da 3n+1 perché se il prodotto di due numeri dispari è anch'esso dispari altrimenti sarebbe divisibile per due ma il due non compare fra i minimi comuni denominatori. Un numero dispari incrementato di uno, diventa pari.

Il passo successivo è (3m+4)/2 quindi 3m/2 + 2. Poiché m è pari allora esiste h per cui m=2h e h=(n-1)/2. 

Quindi 

  • 3(n-1)/4 + 2 = 3n/4 - 3/4 + 2 = 3n/4 + 5/4. 

Per quali n accade che 3n/4 + 5/4 ≥ n?

  • 3n + 5 ≥ 4n quindi 5 ≥ n quindi n ≤ 5 

ma per tutti gli n ≤ 5 la convergenza finita a 1 è verificata quindi per tutti gli n > 5 dispari dopo due passaggi avranno ridotto il loro modulo e a quel punto o sono dispari e vale quanto sopra, oppure sono pari e vengono dimezzati oppure sono inferiori o uguale a 5 ma anche questi convergono.

  • Quindi la serie non diverge mai.

Può finire in un ciclo periodico?

Questo equivale a dire che esiste n per cui al passaggio k si ripresenta n.

Supponiamo che n sia pari, esso verrà diviso a metà fino ad incontrare un suo MCD dispari, allora diciamo m*2^d=n.

Se m>5 allora il suo modulo andrà a diminuire entro due passaggi quindi non potrà formare un ciclo periodico infinito.

Supponiamo che n sia dispari allora vale quanto detto prima e per m≤5 sappiano già che la sequenza terminerà.

Verifica delle condizioni di convergenza

Il calcolo sopra sembra errato per l'apparire di un ulteriore e ingiustificato fattore ½, infatti, siano n = m+1, m = 2h quindi:

  • (3(m+1)+1)/2 = (3m + 4)/2 = 3h + 2

inoltre h = (m/2) = ((n-1)/2) quindi

  • 3((n-1)/2) + 2 ≥ n quindi 3n-3+4 = 3n+1 ≥ 2n

Perciò per ogni n ≥ -1, cioè sempre.

Ma questa è una conclusione completamente diversa da quella mostrata sopra.

Perciò occorre giustificare quel fattore aggiuntivo di ½ di cui sopra.

Un numero intero come vettore su base infinita

Un qualsiasi numero intero è esprimibile come prodotto di numeri primi quindi è esprimibile come vettore con un numero limitato di componenti su una base infinita:

  • base dei numeri primi: { 2, 3, 5, 7, 11, 13, ... }
  • vettore(3): [0, 1, 0, 0, ... ] = 3^1
  • vettore(60): [2, 1, 1, ... ] = 2^2 * 3^1 * 5^1

Inoltre abbiamo due operazioni possibili a(x) = 3x+1 e b(x) = x/2. La funzione a(x) viene utilizzata se è dispari. La funzione b(x) se x è pari.

Poiché la moltiplicazione di un numero dispari x per 3 produce un numero dispari e l’aggiunta di un’unità +1 a un numero dispari 3x si ottiene un numero pari allora a(x) produce sempre un risultato pari perciò si applica immediatamente dopo la funzione b(x) per un numero di volte sufficiente affinché si produca un numero dispari.

Dato x un numero dispari allora il passaggio è s(x) = b^z(a(x)) = y numero dispari. Ovvero z volte la funzione b(.) dopo aver applicato la funzione a(.).

Come si determina lo z volte?

Osserviamo che se x è espresso con la notazione vettoriale di cui sopra allora moltiplicarlo per 3 equivale a sommare il vettore(3) al vettore(x) che è un numero dispari, il quale avrà N componenti positive non tutte nulle C1 ... Cn:

  • [0, 1, 0... ] + [ 0, C1, …, Cn, 0 … ] = [ 0, 1+C1, …, Cn, 0… ]

Il vettore così ottenuto continuerà ad avere in Cn la componente di spettro più alta ma aggiungendo un +1 a questo numero 3x+1 si ottiene che le componenti si ristrutturino su un spettro pari a (3x+1)/2 infatti la nuova componente C’m non potrà essere un numero primo maggiore della metà di 3x+1.

Vediamo perciò le possibilità:

  • se (3x+1)/2=P è un numero primo allora il vettore risultante da a(x) sarà a(x)=[1, 0...0, P, 0…] e in questo caso lo spettro di b(a(x)) sarà amplificato di un fattore 3/2=1.5 volte rispetto al passo precedente, allora la serie sta crescendo.
  • se (3x+1)/(2^z)=P è un numero primo allora il vettore risultante da a(x) sarà a(x)=[z, 0...0, P, 0…] e in questo caso lo spettro di b^z(a(x)) sarà ridotto di un fattore 3/(2^z) rispetto al passo precedente.

Quindi se z=2, allora 0.75× quindi la serie sta decrescendo altrimenti 1.5× e la serie sta crescendo.

La serie del 27 per esempio

Collatz in codifica binaria

La funzione b^z(a(x)) in codifica binaria equivale ad aggiungere un uno a destra (2x+1) e poi sommare il numero (3x+1) quindi elidere tutti gli zeri a partire da destra. Ad esempio per il numero 7 si ha:

Uno zero a destra vi sarà sempre per costruzione (al 100%) ma quale sarà la probabilità di avere un secondo zero a destra?

Genesi ed esegesi dell'ulteriore fattore di divisione per due

Diciamo il 50% perché se supponiamo che il processo Collatz produca un effetto equivalente a quello random sui singoli bit [¹] e questi possono essere solo uno o zero la probabilità di avere un altro zero è del 50%.

[¹] non si sta affermando che la codifica binaria sia totalmente casuale ma si sta affermando che sarò l'n-esimo bit a <0|1> non è possibile fare alcuna previsione sullo stato del bit precedente o su quello successivo.

Sia quindi la sequenza di bit così rappresentata che termina con zero per costruzione:

  • a b c d e f g h i j k l m n o p q 0 ← zero per costruzione

Abbiamo che:

  • la probabilità che q sia 0 è del 50%

  • la probabilità che p sia 0 è del 50% ma p si può elidere solo se q è zero

Quindi la probabilità di elidere uno zero è 100% (il fattore di moltiplicazione asintoticamente tende a 1.5 per n tendente all'infinito), la probabilità di elidere due zeri è 50% (0.75×), la probabilità di elidere tre zeri è 25% (0.375×) e così via.

Più in generale:

  • 50% una sola divisione quindi fattore ½

  • 50% più divisioni quindi fattore minore ½

Il fattore di amplificazione di (3n+1) quindi 3 volte per la moltiplicazione ma poi il +1 ristruttura lo spettro entro un valore massimo di (3n+1)/2 quindi circa di un fattore 1.5 volte. Anche il modulo viene abbattuto almeno di un fattore due quindi anch’esso è limitato da un rapporto inflazionistico dello 1.5 volte.

Per rispondere alla domanda iniziale dobbiamo cercare quale sia la media ponderata delle <z> divisioni /2:

Quindi mediamente il fattore di divisione del modulo è 4 invece che 2 perciò il termine successivo ha l’opportunità di crescere perché lo spettro accessibile si è amplificato di 1.5 volte ma mediamente il modulo viene diminuito di un fattore di 0.75 volte. 

Questo significa che se da una parte lo spettro accessibile si amplia, le componenti tendono a concentrarsi nella parte inferiore. 

Ora applichiamo il fattore di divisione del modulo con un <z> = 2 medio:

  • 3(n-1)/2 + 2 ≥ n diventa 3((n-1)/4 + 2 ≥ n

Quindi

  • 3(n-1) + 8 ≥ 4n
  • 3n -3 +8 ≥ 4n
  • 3n +5 ≥ 4n
  • 5 ≥ n
  • n ≤ 5

Perciò la dimostrazione iniziale era corretta nonostante l’apparenza inizialmente ingiustificata di un fattore ½ ulteriore.

Tavola del calcolo del fattore di divisione medio

Tavola del calcolo delle divisioni in maniera più estesa, valutazione del fattore medio <z> per passaggio b^z(a(x)) di divisione per due:

Osservazioni riguardo alla validità dell'analisi statistica

Perché l'analisi statistica che indica come aggiuntivo un termine di divisione per due avrebbe valore di dimostrazione e non solo di spiegazione di quanto osservato riguardo alla congettura di Collatz?

Per capirlo è opportuno confrontare i seguenti casi.

  • C.1 – supponiamo che il numero 55 del lotto sia in ritardo sulla ruota di Genova di 30 estrazioni. Questo rende più probabile la sua comparsa nella prossima estrazione? No. Perché le estrazioni sono processi indipendenti e quindi ognuna di loro produce risultati assolutamente non correlati con quanto osservato in passato. Perciò il numero 55 ha la stessa probabilità di essere estratto di un altro qualsiasi numero.
  • C.2 – supponiamo che nell'applicare b^z(a(x)) per m volte la media è sensibilmente inferiore a 2. Quindi dovremo aspettarci che nelle successive b^z(a(x)) si verifichino eventi compensativi tali da riportare la media al valore atteso? Si. Perché la sequenza di b^z(a(x)) non sono eventi indipendenti ma altamente correlati, infatti l'intero processo è deterministico. L'osservazione statistica e quindi le sue previsioni è un processo di analisi che si basa sulla nostra ignoranza aprioristica del fenomeno nel suo complesso.

La differenza fra i due fenomeni si può riassumere nella differenza fra generazione casuale di eventi e generatori pseudocasuali di eventi.

In entrambi i casi si può fare un'analisi statistica delle caratteristiche intrinseche del generatore di eventi.

Ma nel primo caso, queste informazioni sono puramente indicative mentre nel secondo caso esse sono caratterizzanti.

Perché nel primo caso l'assunzione che il generatore di eventi permanga invariata è solo un'ipotesi (scommessa) mentre nel secondo caso è una certezza (caratterizzazione).

In questo senso l'analisi statistica del processo di generazione del successivo termine della congettura di Collatz mediante b^z(a(x)) è una caratterizzazione del processo stesso e non una mera ipotesi statistica.

Andiamo a verificare questa asserzione senza l'uso del limite asintotico.

Equivalenza fra l'approccio finito e quello asintotico alla disequazione che impone le condizioni di convergenza sulla serie

Disequazione con fattore t di valore effettivo non asintotico che dipenda dal numero di bit usato per descrivere il numero di partenza della serie:

  • 3((n-1)/2t) + 2 ≥ n

  • 3(n-1) + 4t ≥ 2tn

  • 3n + 4t-3 ≥ 2tn

  • 4t-3 ≥ (2t-3)n

  • (2t-3)n ≤ 4t-3

  • n ≤ (4t-3)/(2t-3)

Con numeri a 4 bit: t=1.625 quindi 

  • n ≤ (4t-3)/(2t-3) = 3.5/0.25 = 4*7/2 = 14.

Con 4 bit si possono esprimere numeri fino a 2⁴ - 1 = 15 ≥ 14 quindi 14 si trova nel range.

Quindi basta verificare che convergano tutte le serie che partano da 14 a scendere.

Con un numero inferiore di bit non serve la disequazione perché è già verificata la convergenza di tutte le serie che partano da numeri a 4 bit.

Con un numero superiore di bit, il fattore t è maggiore di 1.625 quindi si ottiene un limite superiore minore di 14.

Perciò ogni disequazione in t relativa all'uso di un numero arbitrario di bit è riconducibile ai criteri imposti da quella relativa a numeri a 4 bit.

Si noti però che la serie di 7, già ha un termine che è 52 ma anche considerando solo i termini dispari il maggiore è 17 × 2 = 34 quindi servono almeno 6 bit.

Perciò appare non ragionevole eseguire le disequazioni per codifiche più corte di 6 bit.

Con numeri a 6 bit: t=1.875 quindi:

  • n ≤ (4t-3)/(2t-3) = 4.5/0.75 = 18/3 = 6.

Ora, si noti che per le peculiarità della congettura di Collatz un limite n ≤ 6 piuttosto che n ≤ 5 è indifferente in quanto la serie di 6 non è altro che la serie di 3.

Perciò la prima serie rilevante da verificare resta la 5.

Con ciò si può dire che la soluzione di tutte le disequazioni in t coincide con la soluzione della disequazione per t=2 valore asintotico.

Se si esegue Collatz in codifica binaria che è la codifica più semplice in assoluto servono almeno 6 bit e la soluzione della disequazione con t:6bit impone la convergenza per ogni serie che inizi con un numero intero maggiore a 6 quindi 7.

Se si utilizza una codifica binaria illimitata, la disequazione con valore asintotico impone la convergenza di ogni serie che inizi con un numero intero maggiore di 5 ma 6 è pari, quindi 7.

Anche sotto questo punto di vista i due approcci si equivalgono.

D'altronde sarebbe stato sospetto che non si fosse trovata una completa equivalenza fra l'approccio finito e quello asintotico.

Bisogna infine notare che il parametro t non si utilizza come /(2*t) ma come /(2^t) in quanto rappresenta il numero medio di divisioni per due quindi

  • n ≤ (4t-3)/(2t-3)

diventa

  • n ≤ (2*2^t-3)/(2^t-3)

perciò per

  • 6bit, t=1.875: 4.336 / 0.668 = 6.491

quindi

  • n < 7

poiché 6 è pari

  • n ≤ 5

Una condizione esattamente equivalente a quanto sopra detto per ogni codifica a 6 o più bit.

Verifica della convergenza verso il ciclo banale

Abbiamo stabilito che le nessuna delle serie di Collatz può divergere ora però occorre verificare se qualcuna di esse può generare un loop infinito che non sia quello banale C(n) = 4 2 1, 4 2 1, … .

Perciò definiamo la seguente funzione, secondo la nomenclatura precedente per la quale a(n)=3n+1; b(x)=x/2:

  • S(n) = b^z(a(n)) = b(... b(a(n) … ) con z, n numeri interi positivi

allora affinché si generi un ciclo infinito occorre che la ripetizione m volte di S(.) sia

  • S^m(n) = S( … S(n) … ) = n con n, m numeri interi positivi

Allora supponiamo che φ sia un numero reale per il quale S(n) = φ · n dove (φ · n) è un numero intero positivo e dispari allora l'intera serie di Collatz si può scrivere come

  • S^m(n) = φm · ( ... · (φ2 · (φ1 · n))) = (φ1 · φ2 · … · φm) · n

portando fuori dagli m termini moltiplicativi reali le varie parti in 2^w otteniamo che

  • S^m(n) = (ψ1 · ψ2 · … · ψm) · n · 2^w = n con n, w numeri interi positivi

Semplificando e portando dall'altra parte dell'uguale il termine m-esimo

  • (ψ1 · ψ2 · … · ψm-1) · 2^w = 1 / ψm

dove entrambi i termini dell'uguaglianza devono essere dei numeri interi dispari per costruzione:

  • (ψ1 · ψ2 · … · ψm-1) · 2^w = d
  • (ψ1 · ψ2 · … · ψm-2) · 2^w = d / ψm-1
  • (ψ1 · ψ2 · … · ψm-2) · 2^w = d'
  • (ψ1 · ψ2 · … · ψm-3) · 2^w = d' / ψm-2
  • ...
  • ψ1 · 2^w = d" / ψ2
  • ψ1 · 2^w = d'"
  • 2^w = d'" / ψ1
  • 2^w = d""

Quindi il numero dispari d"" dovrebbe essere un numero pari. Assurdo.

Più specificatamente: se una serie di Collatz si conclude in un ciclo infinito, allora esso inizia con una potenza di due quindi 2^w che evolve in 4 2 1, ovvero il ciclo banale che generalmente indichiamo come convergenza della serie.

Conclusione

In attesa di un'eventuale confutazione, pasciamoci di questa conclusione che vede la congettura di Collatz confermata e ammiriamone il frattale che genera quando estesa sul piano dei numeri complessi.

–Fonte: Wikipedia in Inglese

Indice di tutti gli articoli pubblicati

Revisione precedente

Condividi

(C) 2018, Roberto A. Foglietta, testo licenziato con Creative Common Attribuzione, Non commerciale, Condividi allo stesso modo, versione 3.0, Italia (CC BY-NC-SA 3.0 IT).


Roberto A. Foglietta 11/3/2018 · #2

UP.2018.3.11

0
Roberto A. Foglietta 8/3/2018 · #1

Este usuario ha eliminado este comentario

0