Don't take life too seriously: it's just a temporary situation

Thue – Morse (costante di)

Rappresentazione dei numeri  Sequenze 

La sequenza di Thue – Morse è definibile in vari modi:

  • tn è il numero di bit uguali a 1 nella rappresentazione binaria di n, modulo 2, vale a dire 1, se la rappresentazione binaria di n contiene un numero dispari di 1, 0 altrimenti;

  • t0 = 0, t2n = tn e t2n + 1 = 1 – tn per n > 0;

  • si inizia con 0 e si prosegue prendendo la sequenza sino a quel momento ottenuta, invertendola (ossia scambiando 0 con 1) e concatenando ciò che si ottiene alla sequenza stessa;

  • si inizia con 0 e si prosegue sostituendo ogni 0 con 01 e ogni 1 con 10 e ripetendo le sostituzioni all’infinito.

La sequenza di Thue – Morse è quindi: 011010011001011010010110011010011001011001101001011....

 

Per quanto riguarda l’ultima definizione, la sequenza di Thue – Morse è l’unica che resti invariata se sottoposta alla trasformazione descritta. Più in generale le uniche sequenze prive di sovrapposizioni (del tipo awawa, dove w è una sottosequenza qualsiasi, anche vuota, e a è una singola cifra) che restino invariate rispetto a una trasformazione non banale, che sostituisca ogni cifra con una sequenza, senza lasciare inalterata la sequenza iniziale, sono la sequenza di Thue – Morse e il suo complemento, ottenuto scambiando 0 con 1 e viceversa (P. Séébold, 1985).

Brown, Rampersad, Vasiga e Jos dimostrarono che una qualsiasi modifica di un insieme finito di cifre nella sequenza crea una sovrapposizione.

 

La sequenza fu utilizzata per la prima volta da Eugène Prohuet nel 1851, nell’ambito della teoria dei numeri, ma non esplicitamente menzionata.

Fu poi utilizzata da Axel Thue (Tønsberg, Norvegia, 19/2/1863 – Oslo, 7/3/1922) nel 1906 nel calcolo combinatorio, ma il suo lavoro apparve in un’oscura rivista norvegese e fu quasi ignorato.

La sequenza fu infine resa celebre da Harold Calvin Marston Morse (Waterville, USA, 24/3/1892 – Princeton, USA, 22/6/1977), che la utilizzò nell’ambito della geometria differenziale. Fu riscoperta numerose volte indipendentemente da vari matematici.

 

Alcune proprietà della sequenza:

  • (–1)tn è il coefficiente di xn nell’espansione di Prodotto infinito legato alla sequenza di Thue – Morse;

  • [ 0, 0, 1, 0, 0, 1, 1, 1 – t0, 1 – t1, 1 – t2, 1 – t3, ... ] è la minima sequenza infinita priva di sovrapposizioni;

  • se si prende un elemento ogni 2n, cioè uno ogni 2, uno ogni 4 o uno ogni 8 ecc., si ottiene di nuovo la stessa sequenza;

  • Prodotto infinito legato alla sequenza di Thue – Morse (D.R. Woods e D. Robbins 1979).

Da notare la somiglianza tra l’ultima formula e la seguente: Prodotto infinito legato alla sequenza di Golay – Rudin – Shapiro, dove un è la sequenza di Golay – Rudin – Shapiro, cioè il numero di “11”, anche sovrapposti, nell’espansione binaria di n, modulo 2 (in altre parole, un è 1 se nello sviluppo di n in base 2 vi è un numero dispari di sequenze “11”, 0 altrimenti).

 

Definiamo una sequenza come segue: a0 = 0, a1 = 1, poi si prosegue aggiungendo i numeri naturali in ordine, salvo che a2n viene escluso, se an fa già parte della sequenza. La sequenza è quindi: 0, 1, 3, 4, 5, 7, 9, 11, 12, 13, 15, 16, …. Una definizione equivalente è che n non fa parte della sequenza se e solo se la massima potenza di 2 che divide n ha esponente dispari.

La sequenza è legata alla sequenza di Thue – Morse, perché quest’ultima è formata da a1a0 volte 0, seguito da a2a1 volte 1, poi a3a2 volte 0, a4a3 volte 1 e così via.

 

Il problema di Prohuet – Tarry – Escott, dal nome dei matematici che diedero i più rilevanti contributi alla soluzione, consiste nel dividere i numeri naturali da 0 a n – 1 in modo che siano uguali le somme delle potenze con esponente 1 a k degli elementi dei due insiemi. Prohuet dimostrò che il problema è risolubile se n è un multiplo di 2k + 1 – 1 e la sequenza di Thue – Morse fornisce una soluzione generale, suddividendo gli interi da 0 a 2k + 1 – 1 in due insiemi, uno formato dai numeri corrispondenti alle cifre 0 nella sequenza, l’altro formato dai numeri corrispondenti alle cifre 1, numerando le cifre da zero. Per esempio, per k = 3 un insieme è { 0, 3, 5, 6, 9, 10, 12, 15 } e l’altro è { 1, 2, 4, 7, 8, 11, 13, 14 }:

  • 0 + 3 + 5 + 6 + 9 + 10 + 12 + 15 = 1 + 2 + 4 + 7 + 8 + 11 + 13 + 14;

  • 02 + 32 + 52 + 62 + 92 + 102 + 122 + 152 = 12 + 22 + 42 + 72 + 82 + 112 + 132 + 142;

  • 03 + 33 + 53 + 63 + 93 + 103 + 123 + 153 = 13 + 23 + 43 + 73 + 83 + 113 + 133 + 143.

Dato che i due insiemi hanno lo stesso numero di elementi, potremmo anche includere le potenze di esponente 0, con la convenzione che 00 = 1.

Esistono anche alcune soluzioni al problema se n non è un multiplo di 2k + 1 – 1, ma solo con questa condizione i due sottoinsiemi hanno lo stesso numero di elementi.

Inoltre la soluzione basata sulla sequenza di Thue – Morse rende minima la differenza tra le somme delle potenze (k + 1)-esime degli elementi dei due insiemi; è un problema aperto se possano esistere altre suddivisioni con questa proprietà.

 

Un metodo analogo permette di suddividere i numeri naturali da 0 a nk + 1 – 1 in n insiemi, in modo che tutti gli insiemi abbiano uguali somme delle potenze con esponente 1 a k. La sequenza va costruita iniziando con le cifre da 0 a n – 1, concatenando ogni volta le permutazioni cicliche dei blocchi ottenuti al passo precedente. Per esempio, per n = 3 si inizia con 012 e si costruiscono le permutazioni cicliche della sequenza, cioè 012 120 201, poi le permutazioni cicliche dei blocchi ora ottenuti, quindi 012120201, 120201012 e 201012120, proseguendo per k passi, sino a ottenere una sequenza di nk + 1 simboli, che ci diranno come ripartire gli interi in k insiemi.

Una definizione equivalente, risalente allo stesso Prohuet, è che la cifra m-esima (iniziando da zero) è la somma delle cifre nella rappresentazione in base n di m, presa modulo n.

Nell’esempio, i 3 insiemi con k = 2 sono { 0, 5, 7, 11, 13, 15, 19, 21, 26 }, { 1, 3, 8, 9, 14, 16, 20, 22, 24 } e { 2, 4, 6, 10, 12, 17, 18, 23, 25 }; infatti:

  • 0 + 5 + 7 + 11 + 13 + 15 + 19 + 21 + 26 = 1 + 3 + 8 + 9 + 14 + 16 + 20 + 22 + 24 = 2 + 4 + 6 + 10 + 12 + 17 + 18 + 23 + 25;

  • 02 + 52 + 72 + 112 + 132 + 152 + 192 + 212 + 262 = 12 + 32 + 82 + 92 + 142 + 162 + 202 + 222 + 242 = 22 + 42 + 62 + 102 + 122 + 172 + 182 + 232 + 252.

Una volta ottenuti insiemi di questo genere, è possibile moltiplicare tutti gli elementi per uno stesso intero o sommare a tutti lo stesso intero, ottenendo un altro gruppo di insiemi con la stessa proprietà.

 

Nel 1959 J. Lambek e Leo Moser dimostrarono che se si suddividono tutti gli interi positivi in due insiemi infiniti, utilizzando la sequenza di Thue – Morse come mostrato sopra, i numeri ottenibili come somma di elementi distinti del primo insieme sono esattamente quelli ottenibili come somma di elementi distinti del secondo insieme e che il numero di modi per ottenerli è uguale nei due casi. Per esempio, 15 può essere ottenuto in 4 modi dal primo insieme (0 + 15, 3 + 12, 5 + 10 e 6 + 9) e in altrettanti dal secondo (1 + 14, 2 + 13, 4 + 11 e 7 + 8).

I due matematici dimostrarono anche che questa è l’unica suddivisione degli interi in due insiemi che goda di queste proprietà. Se e solo se si utilizzano solo i primi 2k termini della sequenza, per qualsiasi valore intero di k, si ottengono due insiemi finiti che hanno ancora le stesse proprietà.

I due infine dimostrarono che i due insiemi { 1, 6, 8, 10, 12, 14, 15, … } e { 2, 3, 4, 5, 7, 9, 11, 13, … } godono delle stesse proprietà rispetto alla moltiplicazione, invece che all’addizione; in questo caso però i due insiemi devono essere infiniti, perché se ci si arresta in qualsiasi punto, le proprietà non valgono. Per stabilire in quale insieme vada ogni numero bisogna scomporlo in fattori primi e considerare il numero totale di 1 nella rappresentazione binaria degli esponenti dei fattori: se tale numero è pari va nel primo insieme, altrimenti nel secondo. Per esempio, 12 = 2231 e dato che sia 2 che 1 rappresentati in notazione binaria contengono un solo 1, il numero totale di 1 è pari e 12 va nel primo insieme.

 

Nella sequenza di Thue – Morse non ci sono mai più di due cifre uguali di seguito, né più di due sottosequenze uguali consecutive; in effetti, il matematico norvegese la definì come soluzione al problema di costruire una sequenza infinita, che non contenesse più di due ripetizioni consecutive della stessa sottosequenza, utilizzando due soli simboli.

E’ abbastanza facile dimostrare che una sequenza del genere deve contenere sottosequenze identiche adiacenti: iniziando con 1 si è costretti ad aggiungere uno 0 e quindi un 1, per evitare ripetizioni di “blocchi” di una cifra, ma a questo punti si ha 101 e non si può aggiungere un’altra cifra senza ripetere un blocco; un ragionamento simmetrico mostra che non si può neppure iniziare con 0. Non è però affatto ovvio che si possano evitare le ripetizioni di tre sottosequenze identiche consecutive; Thue dimostrò che la sequenza non contiene ripetizioni del genere, ma neppure sovrapposizioni, affermazione più forte, perché una tripla ripetizione implica una sovrapposizione, ma non viceversa.

 

Entringer e Jackson dimostrarono nel 1974 che esiste una sequenza infinita di due soli simboli che non ha blocchi adiacenti di 3 o più simboli (quindi contiene solo ripetizioni di singole cifre o blocchi di due), mentre ogni sequenza di due soli simboli lunga almeno 18 simboli deve contenere due blocchi adiacenti di lunghezza almeno 2.

Due anni dopo Dekking dimostrò che esistono infinite sequenze di due soli simboli che non contengono tre ripetizioni di uno stesso blocco (incluse le cifre singole).

 

Se nella sequenza di Thue – Morse si sostituisce alla cifra n-esima il numero di 1 tra l’n-esimo zero e l’(n + 1)-esimo, si ottiene la sequenza 210201210120210201202101210201…, che, pur essendo formata con tre soli simboli, non contiene due blocchi uguali adiacenti, di qualsiasi numero di cifre (quindi neppure due cifre uguali consecutive), come dimostrò lo stesso Thue.

 

La sequenza di Thue – Morse ha un curioso legame con gli scacchi: in base alle regole cosiddette “tedesche”, in vigore in vari stati, inclusa la Germania, nel 1929, una partita poteva essere dichiarata patta se la stessa sequenza di mosse veniva ripetuta tre volte di seguito. Il futuro campione mondiale Machgielis Euwe (1901 – 1981) reinventò la sequenza e si servì della proprietà dell’assenza di tre sottosequenze identiche consecutive per dimostrare che la regola poteva portare a partite di lunghezza infinita, anche se i giocatori si fossero limitati a far ciondolare un paio di pezzi a testa avanti e indietro tra due caselle. Come conseguenza venne accettata la regola oggi universale che un giocatore può richiedere che la partita sia dichiarata patta se la stessa posizione si ripresenta tre volte, indipendentemente da come sia raggiunta.

 

La costante di Thue – Morse, detta anche “costante della parità” o “costante di Prohuet – Thue – Morse”, è definita è definita come il valore rappresentato dalla sequenza, considerata come lo sviluppo in base 2 di un numero, ovvero come Formula per la definizione della costante di Thue – Morse, dove tn è l’n-esimo numero della sequenza di Thue – Morse.

Qui trovate le prime 10000 cifre binarie della costante di Thue – Morse, corrispondenti ad altrettanti termini della sequenza di Thue – Morse (N.J.A. Sloane, The Online Encyclopedia of Integer Sequences http://oeis.org).

Qui trovate le prime 10000 cifre decimali della costante di Thue – Morse (Harry J. Smith, The Online Encyclopedia of Integer Sequences http://oeis.org).

 

Alle voci espansione di Engel, espansione di Lehmer, frazioni continue e frazioni continue centrate si trovano ottime approssimazioni della costante.

 

La costante si può anche definire come limite della ricorrenza a0 = 0, Ricorrenza per la definizione della costante di Thue – Morse.

 

Lo sviluppo della costante come frazione continua semplice non presenta evidenti simmetrie o regolarità, ma si può rappresentare la costante come frazione continua non regolare in modo relativamente semplice: Frazione continua uguale alla costante di Thue – Morse.

Dopo i primi due termini, gli interi prima del segno meno sono ciascuno il quadrato del precedente e i numeratori sono uguali al numero che li precede meno uno.

La frazione è strettamente legata al prodotto infinito Prodotto infinito che converge alla costante di Thue – Morse, che converge alla costante.

 

Nello sviluppo in frazione continua della costante si trovano lunghe sequenze di termini piccoli, separate da occasionali termini maggiori, che sembrano crescere; Y. Bugeaud diede un senso matematicamente più preciso a queste osservazioni, dimostrando nel 2011 che lo sviluppo in frazione continua semplice ha infiniti termini uguali a 4 o 5 e infinite coppie di termini consecutivi non superiori a 5.

 

Kurt Mahler dimostrò nel 1929 che la costante è trascendente; una dimostrazione indipendente fu trovata da F.M. Dekking nel 1977; con un errore secondario che venne in seguito corretto. Più in generale sono trascendenti i numeri Formula che definisce una famiglia infinita di numeri trascendenti per qualsiasi intero b maggiore di 1.

 

Boris Adamczewski e Tanguy Rivoal dimostrarono che la misura di irrazionalità della costante di Thue – Morse è al Massimo 4 (v. numeri di Liouville).

 

M. Drmota, Christian Mauduit, e J. Rivat dimostrarono nel 2013 che se si estraggono le sole cifre che hanno per indice un quadrato (quindi prima, quarta, nona ecc.) si ottiene un numero normale in base 2.

un paio di pezzi avanti e indietro tra due caselle

Bibliografia

  • Honsberger, Ross;  Mathematical Diamonds, The Mathematical Association of America, 2003 -

    Una stupenda raccolta di saggi su argomenti disparati.

  • Odifreddi, Piergiorgio;  "Giochiamo a pari e dispari" in Le Scienze, Milano, n. 449, gennaio 2006, pag. 111.
  • Roberts, Joe;  The Lure of the Integers, The Mathematical Association of America, 1992 -

    Una miniera di informazioni sugli interi.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.