Lasuccessione di Thue-Morse, chiamata anchesuccessione di Prouhet-Thue-Morse, è una sequenza dicifre binarie che trova applicazioni in vari settori dellamatematica.

Lasuccessione inizia con:^[1]

0110100110010110100101100110100110010110011010010110100110010110...

Agli 0 e agli 1 si può sostituire qualunque altracoppia di simboli, senza che la struttura logica della successione ne risenta^[2].

La successione di Thue-Morse è stata originariamente studiata dal matematicoEugène Prouhet nel 1851, che la applicò allateoria dei numeri senza però definirla esplicitamente^[3]. Il primo a farlo fu, nel 1906,Axel Thue, che usò la sequenza per fondare lacombinatoria delle parole^[4][5]. Tuttavia, la successione fu portata all'attenzione della comunità internazionale solo nel 1921, grazie al lavoro diMarston Morse che la applicò allageometria differenziale^[6].

La successione di Thue-Morse è stata riscoperta indipendentemente diverse volte, anche da matematici non professionisti. Per esempio ilgran maestro di scacchi, ex-campione del mondo edocente di matematicaMax Euwe ha scoperto nel 1929 un modo di usare la successione per aggirare una regola degliscacchi che considera la partita finita in patta in caso di ripetizioni continuate di sequenze di mosse (a quei tempi la regola richiedeva che le posizioni ripetute della scacchiera fossero consecutive, è stata poi modificata in modo che la triplice ripetizione anche non consecutiva di una posizione facesse terminare con una patta la partita) e prolungare infinitamente il gioco^[7], sfruttando la sua proprietà di essere priva di sottostringhe ripetute tre volte consecutive.

Esistono diversi modi equivalenti di definire la successione di Thue-Morse.

L'${\displaystyle n}$-esimo numero della successione di Thue-Morse è 0 se l'espressione din inbase 2 contiene un numero pari di 1, ed è uno se ne contiene una quantità dispari. Per esempio l'espressione binaria del numero 5 è 101, che contiene due cifre 1: quindi il quinto simbolo della successione di Thue-Morse è 0. Denotiamo con${\displaystyle t_n}$ l'${\displaystyle n}$-esimo numero della successione di Thue-Morse. Il matematicoJohn Conway ha definitonumero odioso^[8] ogni numero intero${\displaystyle n}$ tale che${\displaystyle t_n=1}$ enumero malvagio^[9] ogni numero intero tale che${\displaystyle t_n=0}$ (si tratta di ungioco di parole, nellalingua inglese, traodious eevil, che significano "odioso" e "malvagio", eodd edeven, che significano "dispari" e "pari").

La successione di Thue-Morse è la sequenza che soddisfa la proprietà che, se${\displaystyle t_n}$ è l'${\displaystyle n}$-esimo elemento della successione di Thue-Morse, allora:

${\displaystyle t_0=0;}$

${\displaystyle t_{2n}=t_n,}$

${\displaystyle t_{2n+1}=1-t_n,}$

per qualunque numero intero positivo${\displaystyle n.}$

La successione di Thue-Morse è l'output del seguentesistema di Lindenmayer:

variabili 0 1costanti nessunainizio 0regole (0 → 01), (1 → 10)

Questo significa che può essere ottenuta iniziando da uno 0 e operando la sostituzione tutti gli 0 con 01 e tutti gli 1 con 10, e ripetendola all'infinito. Si noti che questo procedimento lascia invariati i valori iniziali della stringa, mentre ogni iterazione raddoppia il numero di cifre.

La successione di Thue-Morse, se considerata come sequenza di bit, può essere definitaricorsivamente mediante lanegazione, aggiungendo a ogni passaggio alla sequenza il suo esatto opposto. Quando si posseggono i primi 2ⁿ elementi della stringa, si può così conoscerne i successivi 2ⁿ, che consistono nel bit opposto alla prima metà. Per esempio, sapendo che il primo bit è uno 0, dato che la sua negazione è 1 il bit successivo sarà 1; e dato che la negazione di 01 è 10 i successivi due bit saranno 10; e così via. I primi passaggi sono i seguenti:

• T₀ = 0.
• T₁ = 01.
• T₂ = 0110.
• T₃ = 01101001.
• T₄ = 0110100110010110.
• T₅ = 01101001100101101001011001101001.
• T₆ = 0110100110010110100101100110100110010110011010010110100110010110.

La successione di Thue-Morse può essere definita come la successione di 0 e 1 che soddisfa la seguente relazione:

${\displaystyle \prod _{i=0}^{\mathrm{\infty }}(1-x^{2^i})=\sum _{n=0}^{\mathrm{\infty }}(-1{)}^{t_n}{x}^n,}$

sempre considerando${\displaystyle t_n}$ come l'${\displaystyle n}$-esimo elemento della successione.

Essendo la successione di Thue-Morse costruibile per negazioni e aggiunte successive, tramite il metodo della negazione dei blocchi di bit, essa contiene molti quadrati: ossiasottostringhe ripetute nella formaxx, dovex è una sequenza di bit. Non ci sono invece cubi, cioè stringhe nella formaxxx^[11]. Non vi sono nemmeno quadrati sovrapposti, cioè stringhe 0x0x0 oppure 1x1x1.^[12] Per tutti gli${\displaystyle n>1}$, il pezzo della successione di Thue-Morse dall'inizio a${\displaystyle t_{2n}}$ èpalindroma. Inoltre, contando gli 1 tra due 0 consecutivi in${\displaystyle t_{2n}}$ (cioè fino a${\displaystyle t_{2^n}}$) e chiamando${\displaystyle q_n}$ come la stringa ottenuta concatenando tali valori (per esempio${\displaystyle q_1=2}$ e${\displaystyle q_2=2102012}$),${\displaystyle q_n}$ è sempre una stringa palindroma epriva di quadrati^[11]. Questo perché${\displaystyle T_n}$ non contiene mai quadrati sovrapposti e${\displaystyle T_n}$ è sempre palindromo.

La successione di Thue-Morse, pur non essendo unasuccessione periodica, è unasequenza ricorrente: ciò vuol dire che, prendendo una qualunque stringa${\displaystyle x}$ al suo interno, esiste sempre una lunghezza${\displaystyle L_x}$ (solitamente molto più grande della lunghezza di${\displaystyle x}$) tale che qualunque pezzo della successione contenga sempre${\displaystyle x}$ almeno una volta. L'esponente critico della successione è 2.^[13] Definendo un'endofunzione${\displaystyle f(S)}$ sull'insieme delle sequenze binarie, che operi su una sequenza sostituendo tutti gli 0 con 01 e tutti gli 1 con 10, la successione di Thue-Morse rimarrà invariata dall'applicazione di${\displaystyle f}$: ossia${\displaystyle f(T)=T}$, e${\displaystyle T}$ è dunque unpunto fisso di${\displaystyle f}$. L'unico altro punto fisso è quello che si ottiene negando la successione di Thue-Morse stessa, ossia sostituendo tutti gli 0 con 1 e viceversa; si tratta quindi sostanzialmente dell'unico punto fisso della funzione${\displaystyle f}$.

Definendo${\displaystyle F(x)}$ come lafunzione generatrice della successione di Thue-Morse nelcampo finito${\displaystyle \mathrm{G}\mathrm{F}(2)}$:

${\displaystyle F(x)=0+1x+1x^2+0x^3+1x^4+\dots }$

si può dimostrare che${\displaystyle F}$ soddisfa l'equazione quadratica:

${\displaystyle (1+x)F^2+F\equiv \frac{x}{1+x^2}(\mathrm{mod}2).}$

Questa equazione ha due soluzioni: la successione di Thue-Morse e la sua complementare, che si ottiene sostituendo gli 0 con gli 1 e gli 1 con gli 0.

Valgono le seguenti relazioni:^[14][15]

${\displaystyle \prod _{n=0}^{\mathrm{\infty }}{\left(\frac{2n+1}{2n+2}\right)}^{(-1{)}^{t_n}}=\frac{\sqrt{2}}{2};}$

${\displaystyle \prod _{n=0}^{\mathrm{\infty }}{\left(\frac{2n+1}{2n+2}\right)}^{2t_n}\left(\frac{2n+3}{2n+2}\right)=\frac{2\sqrt{2}}{\pi };}$^[12]

${\displaystyle \prod _{n=0}^{\mathrm{\infty }}{\left(\frac{2n+1}{2n+2}\right)}^{2(1-t_n)}\left(\frac{2n+3}{2n+2}\right)=\frac{\sqrt{2}}{\pi }.}$^[12]

Ilproblema di Prouhet-Tarry-Escott chiede di trovare, dati due numeri interi${\displaystyle a>0}$ e${\displaystyle p\ge 0}$, unapartizione dell'insieme deinumeri naturali da 0 ad${\displaystyle a-1}$ in duesottoinsiemidisgiunti tali che ognuna delle somme delle potenze fino alla${\displaystyle p}$-esima dei rispettivi elementi sia la stessa, ovvero:

${\displaystyle \sum _{x\in S_0}{x}^r=\sum _{x\in S_1}{x}^r}$

per ogni esponente intero${\displaystyle r}$ da 1 a${\displaystyle p}$. Il problema ha sempre almeno una soluzione se${\displaystyle a}$ è unmultiplo di${\displaystyle 2^{p+1}}$, che si ottiene mettendo nel sottoinsieme${\displaystyle S_0}$ i numeri${\displaystyle n}$ per cui${\displaystyle t_n=0}$ (cioè i numeri malvagi) e nel sottoinsieme${\displaystyle S_1}$ i numeri${\displaystyle n}$ per cui${\displaystyle t_n=1}$ (i numeri odiosi), o viceversa.

Dato un qualunque insieme${\displaystyle S}$ di${\displaystyle a}$ elementi disponibili in unaprogressione aritmetica, dalteorema binomiale segue inoltre che se${\displaystyle a}$ è unmultiplo di${\displaystyle 2^{p+1}}$ esiste sempre almeno una partizione dell'insieme delle${\displaystyle p}$-esime potenze degli elementi di${\displaystyle S}$ in due sottoinsiemi le cui somme degli elementi siano uguali.

Ungrafico di Turtle è una curva ottenuta in base a una sequenza e a uno schema di istruzioni prefissato. La successione di Thue-Morse codifica lacurva di Koch, usando come input e le seguenti istruzioni:

• se${\displaystyle t(n)=0}$, vai avanti di una unità di lunghezza;
• se${\displaystyle t(n)=1}$, ruota in senso antiorario di 60°.

Ciò illustra la naturaautosomigliante della successione^[16].

La successione di Thue-Morse fornisce una soluzione ai problemi di distribuzione di risorse tra due contendenti. Per esempio, se A e B vogliono spartirsi un gruppo di elementi, volendo trovare un modo per evitare che uno dei due abbia la possibilità di scegliere elementi di qualità maggiore occorre che ad A spetti la 1°, 4°, 6°, 7°, ecc. scelta (uno più i numeri ordinali malvagi) e a B la 2°, 3°, 5°, 8°, ecc. scelta (uno più i numeri odiosi). Questa proprietà può anche essere applicata, per esempio, per suddividere il contenuto di una caffettiera in un dato numero di tazze di caffè con uguale concentrazione disoluti, e quindi con uguale sapore^[17][18].Questo è stato provato dal matematicoRobert Richman che, pur senza nominare esplicitamente la successione, ha descritto le relazioni dellefunzioni gradino descritte da T_n nell'intervallo [0,1] con lafunzione di Walsh e lafunzione di Rademacher. Richman ha mostrato che la loron-esimaderivata può essere espressa in termini di T_n, e che quindi la funzione a gradino descritta da T_n èortogonale aipolinomi digradon-1^[17].

Questa sezione sull'argomento matematica è ancora vuota.Aiutaci a scriverla!

• (EN) Jean-Paul Allouche eJeffrey Shallit,Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, 2003,ISBN 978-0-521-82332-6,Zbl 1086.11015.
• (EN) Jean Berstel, Aaron Lauve, Christophe Reutenauer e Franco V. Saliola,Combinatorics on words. Christoffel words and repetitions in words, CRM Monograph Series, vol. 27, Providence, RI, American Mathematical Society, 2009,ISBN 978-0-8218-4480-9,Zbl 1161.68043.
• Yann Bugeaud,Distribution modulo one and Diophantine approximation, Cambridge Tracts in Mathematics, vol. 193, Cambridge, Cambridge University Press, 2012,ISBN 978-0-521-11169-0,Zbl pre06066616.
• (EN) M. Lothaire,Algebraic combinatorics on words, With preface by Jean Berstel and Dominique Perrin, Encyclopedia of Mathematics and Its Applications, vol. 90, Reprint of the 2002 hardback, Cambridge University Press, 2011,ISBN 978-0-521-18071-9,Zbl 1221.68183.
• (EN) M. Lothaire,Applied combinatorics on words, A collective work by Jean Berstel, Dominique Perrin, Maxime Crochemore, Eric Laporte, Mehryar Mohri, Nadia Pisanti, Marie-France Sagot, Gesine Reinert, Sophie Schbath, Michael Waterman, Philippe Jacquet, Wojciech Szpankowski, Dominique Poulalhon, Gilles Schaeffer, Roman Kolpakov, Gregory Koucherov, Jean-Paul Allouche and Valérie Berthé, Encyclopedia of Mathematics and Its Applications, vol. 105, Cambridge, Cambridge University Press, 2005,ISBN 0-521-84802-4,Zbl 1133.68067.
• (EN) N. Pytheas Fogg,Substitutions in dynamics, arithmetics and combinatorics, Editors Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A., Lecture Notes in Mathematics, vol. 1794, Berlin, Springer-Verlag, 2002,ISBN 3-540-44141-7,Zbl 1014.11015.
• (EN) Allouche, J.-P. and Cosnard, M. "The Komornik-Loreti Constant Is Transcendental."Amer. Math. Monthly107, 448-449, 2000.
• (EN) Allouche, J.-P. and Shallit, J. "The Ubiquitous Prouhet-Thue-Morse Sequence." InSequences and Their applications, Proc. SETA'98 (Ed. C. Ding, T. Helleseth, and H. Niederreiter). New York: Springer-Verlag, pp. 1–16, 1999.
• (EN) Allouche, J.-P. and Shallit, J. "Example 5.1.2 (The Thue-Morse Sequence)."Automatic Sequences: Theory, Applications, Generalizations. Cambridge, England: Cambridge University Press, pp. 152–153, 2003.

• Costante di Prouhet-Thue-Morse
• Grafico di Turtle
• Funzione generatrice
• Successione di Rudin-Shapiro

• Wikimedia Commons contiene immagini o altri file sullasuccessione di Thue-Morse

• (EN) Eric W. Weisstein,Thue-Morse Sequence, suMathWorld, Wolfram Research.
• (EN) Allouche, J.-P.; Shallit, J. O.The Ubiquitous Prouhet-Thue-Morse Sequence
• (EN)Reducing the influence of DC offset drift in analog IPs using the Thue-Morse Sequence.
• Esposizione divulgativa della successione di Thue-Morse, suxmau.wikispaces.com.
• (EN)Thue-Morse sequence tilings and patternsArchiviato il 27 aprile 2012 inInternet Archive.: immagini generate dalla successione di Thue-Morse
• (EN)MusiNum - The Music in the Numbers: Software per generare musica autosomigliante dalla successione di Thue-Morse e da altre sequenze analoghe

V · D · M Teoria dei numeri
Numeri più usati	Naturali ·Interi ·Pari e dispari
Principi generali	Principio d'induzione ·Principio del buon ordinamento ·Relazione di equivalenza
Successioni di interi	Fattoriale ·Successione di Fibonacci ·Numero di Catalan ·Numero di Perrin ·Numero di Eulero ·Successione di Mian-Chowla ·Successione di Thue-Morse
Caratteristiche dei numeri primi	Numero primo ·Lemma di Euclide ·Teorema dell'infinità dei numeri primi ·Crivello di Eratostene ·Test di primalità ·Teorema fondamentale dell'aritmetica ·Interi coprimi ·Identità di Bézout ·MCD ·mcm ·Algoritmo di Euclide ·Algoritmo esteso di Euclide ·Teorema dei numeri primi
Funzioni aritmetiche	Funzione moltiplicativa ·Funzione additiva ·Convoluzione di Dirichlet ·Funzione φ di Eulero ·Funzione di Möbius ·Funzione tau sui positivi ·Funzione sigma ·Funzione di Liouville ·Funzione di Mertens
Aritmetica modulare	Teorema cinese del resto ·Piccolo teorema di Fermat ·Teorema di Eulero ·Criteri di divisibilità ·Teorema di Fermat sulle somme di due quadrati ·Teorema di Wilson ·Legge di reciprocità quadratica
Congetture	Congettura di Goldbach ·Congettura di Polignac ·Congettura abc ·Congettura dei numeri primi gemelli ·Congettura di Legendre ·Nuova congettura di Mersenne ·Congettura di Collatz ·Ipotesi di Riemann
Altro	Problema di Waring
Principali teorici	Fibonacci ·Fermat ·Gauss ·Eulero ·Legendre ·Riemann ·Dirichlet
Discipline connesse	Teoria algebrica dei numeri ·Teoria analitica dei numeri ·Crittografia ·Teoria computazionale dei numeri

Portale Matematica: accedi alle voci di Wikipedia che trattano di Matematica

• Combinatoria
• Punti fissi
• Successioni di interi

• Voci con modulo citazione e parametro pagine
• Aggiungere sezioni - matematica
• P2812 letta da Wikidata
• Template Webarchive - collegamenti all'Internet Archive