The Thue-Morse Transform

Il paper introduce la trasformata di Thue-Morse, definendola attraverso i numeri "evil" e "odiosi" delle sequenze binarie, e dimostra come le sue iterazioni sulla sequenza classica generino nuove famiglie di soluzioni al problema di Prouhet-Tarry-Escott, estendano le formule composte classiche e permettano di determinare la complessità fattoriale per i livelli di Mersenne, oltre a proporre generalizzazioni in base $d$ e un analogo basato sulla numerazione di Zeckendorf.

L'essenziale

Immagina di avere una macchina magica che prende una sequenza di numeri (fatta solo di 0 e 1, come un codice binario) e la trasforma in una nuova sequenza, completamente diversa ma strettamente collegata alla prima. Questo è il cuore del lavoro di Benoît Cloitre: l'introduzione della "Trasformazione Thue-Morse".

Ecco una spiegazione semplice, usando metafore quotidiane, di cosa succede in questo articolo scientifico.

1. La Macchina Trasformatrice (Il Concetto Base)

Immagina una lunga fila di persone, ognuna con un cartellino che dice "0" o "1".

• La macchina guarda questa fila.
• Prende tutti quelli con il cartellino "0" e li mette in una lista speciale chiamata "Numeri Cattivi" (in matematica si chiamano evil numbers).
• Prende tutti quelli con il cartellino "1" e li mette in un'altra lista chiamata "Numeri Malvagi" (o odious numbers).
• Poi, usa queste due liste per costruire una nuova fila di persone.

La regola è semplice: se nella lista originale la persona era in una posizione "cattiva", nella nuova fila avrà lo stesso valore. Se era in una posizione "malvagia", nella nuova fila avrà il valore opposto (se era 0 diventa 1, e viceversa).

Questa è la Trasformazione Thue-Morse. È come se prendessi una ricetta, la leggessi, e poi usassi gli ingredienti in un ordine diverso per creare un nuovo piatto che ha lo stesso sapore di base ma una struttura diversa.

2. La Torre di Sequenze (L'Iterazione)

Il punto geniale dell'articolo è: cosa succede se ripeti la magia?

• Prendi la sequenza originale (chiamiamola "Seme").
• Applica la macchina: ottieni la Sequenza 1.
• Prendi la Sequenza 1, applica di nuovo la macchina: ottieni la Sequenza 2.
• E così via...

Crei una torre infinita di sequenze. L'autore scopre che ogni livello di questa torre non è casuale, ma segue una regola matematica precisa e bellissima, come un frattale che si ripete all'infinito.

3. La "Maschera" Segreta (La Formula Chiave)

Come si può descrivere ogni livello di questa torre senza dover calcolare tutto passo dopo passo?
L'autore trova una "Maschera" (un filtro digitale).
Immagina che ogni numero sia scritto in codice binario (come 10110). Ogni livello della torre ha una sua "maschera" specifica.

• Se il numero ha un "1" in una posizione dove la maschera ha un "0", quel numero conta.
• Se la maschera ha un "1" in quella posizione, quel numero viene ignorato.

La sequenza finale è semplicemente la somma (parità) di tutti i "1" che sono stati lasciati passare dalla maschera. È come se ogni livello della torre fosse un filtro diverso che seleziona quali bit del numero originale sono importanti. Più sali nella torre, più il filtro diventa complesso e specifico.

4. Il Problema della Bilancia (Prouhet-Tarry-Escott)

A cosa serve tutto questo? Serve a risolvere un antico rompicapo matematico: come dividere un gruppo di numeri in due squadre in modo che le loro somme siano uguali?
Non solo la somma, ma anche la somma dei quadrati, dei cubi, ecc.

• Il vecchio metodo: Sapevamo come farlo per un certo livello di complessità (usando la sequenza originale).
• La nuova scoperta: Questa "torre" di trasformazioni ci permette di creare nuove squadre perfette per livelli di complessità molto più alti.
  • Immagina di dover dividere 1000 persone in due gruppi. Se vuoi che la somma delle loro età sia uguale, è facile. Se vuoi che la somma dei cubi delle loro età sia uguale, è difficilissimo.
  • Con la "Maschera" di Cloitre, puoi scegliere quale livello della torre usare per ottenere una divisione perfetta anche per potenze molto alte. È come avere un set di chiavi inglesi di tutte le dimensioni per aprire qualsiasi lucchetto matematico.

5. Le Regole di Movimento (Numeri "Cattivi" e "Malvagi")

L'articolo studia anche come si muovono le persone nelle liste "Cattive" e "Malvage" quando si sale di livello nella torre.

• Nel caso semplice (il livello 0), le regole sono fisse e prevedibili (come un orologio che ticchetta sempre allo stesso modo).
• Nei livelli superiori, le regole diventano più complicate: non sono più costanti, ma seguono uno schema che cambia in modo intelligente (automatico). È come se l'orologio avesse un meccanismo interno che accelera o rallenta in base alla posizione, ma sempre seguendo una legge precisa.

6. Oltre il Binario (Estensioni)

L'autore mostra che questa macchina non funziona solo con i numeri 0 e 1 (binario).

• Base 10 o altre: Si può adattare la macchina per funzionare con numeri in base 3, 4, 10, ecc.
• Altre sequenze: Si può usare la macchina non solo sulla sequenza classica, ma anche su altre sequenze speciali (come quelle legate alla successione di Fibonacci, i numeri che appaiono nei girasoli e nelle conchiglie). Anche lì, la macchina crea strutture interessanti, anche se un po' diverse.

In Sintesi

Questo articolo ci dice che:

1. Esiste una macchina matematica che trasforma sequenze di numeri in nuove sequenze.
2. Ripetendo la macchina, si crea una torre infinita di sequenze, ognuna con una sua "maschera" segreta.
3. Questa torre ci dà nuovi strumenti potenti per dividere i numeri in gruppi perfetti (risolvendo problemi antichi).
4. Le regole che governano queste trasformazioni sono più ricche e interessanti di quanto pensassimo, rivelando una struttura nascosta e ordinata nel caos apparente dei numeri.

È come se avessimo scoperto che, dietro a un semplice gioco di "0 e 1", c'è un intero universo di strutture matematiche ordinate, pronte a essere esplorate.

Sommario tecnico

1. Il Problema e il Contesto

Il punto di partenza della ricerca è l'operatore noto come Trasformata di Thue-Morse (TM-transform), definito su sequenze binarie. Mentre la sequenza di Thue-Morse classica ($t(n)$) è ben studiata nel contesto del problema di Prouhet-Tarry-Escott (PTE) e delle proprietà combinatorie, questo articolo si propone di studiare le iterazioni di questa trasformata.

Il problema centrale è comprendere la struttura aritmetica e combinatoria della "torre" di sequenze binarie ottenuta iterando la trasformata partendo dalla sequenza classica di Thue-Morse. Nello specifico, l'autore indaga:

• Esiste una forma chiusa esplicita per le iterazioni successive?
• Come si generalizzano le identità di Prouhet-Tarry-Escott (partizioni con somme uguali di potenze)?
• Qual è il comportamento delle "numerazioni malvagie" (evil) e "malvagie" (odious) generalizzate associate a queste iterazioni?
• Qual è la complessità dei fattori (subword complexity) di queste nuove sequenze?

2. Metodologia

L'approccio metodologico combina la teoria dei numeri, la teoria delle sequenze automatiche e l'analisi combinatoria delle parole.

• Definizione della Trasformata: Data una sequenza binaria $\sigma$ (con $\sigma(0)=0, \sigma(1)=1$), si definiscono i numeri evil ($v_\sigma$) come le posizioni degli 0 e i numeri odiosi ($u_\sigma$) come le posizioni degli 1. La trasformata $T(\sigma) = \tau$ è definita ricorsivamente da $\tau(v_\sigma(n)) = \tau(n)$ e $\tau(u_\sigma(n)) = 1 - \tau(n)$.
• Iterazione: Si costruisce una torre di sequenze $a_0 = t$ (Thue-Morse classica) e $a_{m+1} = T(a_m)$.
• Forma Chiusa (Bit-Mask): L'autore dimostra che ogni iterata $a_m(n)$ ammette una rappresentazione esplicita basata su una "maschera" binaria $m$. La sequenza è data dalla parità dei bit di $n$ le cui posizioni sono disgiunte dal supporto binario di $m$.
• Strumenti Analitici:
  • Funzioni Generatrici: Generalizzazione del metodo di Borwein e Ingalls per dimostrare le identità di PTE.
  • Equazioni Funzionali: Studio delle composizioni delle funzioni inverse (numeri evil/odiosi generalizzati).
  • Desostituzione: Analisi della complessità dei fattori attraverso la sequenza derivata ($\Delta(n) = a_m(n) \oplus a_m(n+1)$).
  • Generalizzazioni: Estensione a basi $d$-arie e analoghi basati sulla numerazione di Zeckendorf (Fibonacci).

3. Contributi Chiave e Risultati Principali

A. Forma Chiusa Esplicita e Struttura della Torre

Il risultato fondamentale è la formula esplicita per l'$m$-esima iterata:
$$a_m(n) = \bigoplus_{p \ge 0, \, p \& m = 0} b_p(n)$$
dove $b_p(n)$ è il $p$-esimo bit di $n$, $\oplus$ è la somma XOR, e $p \& m = 0$ indica che la posizione del bit non è "mascherata" da $m$.

• Questo dimostra che la trasformata iterata non è un processo caotico, ma genera una famiglia di sequenze automatiche con una struttura dyadica chiara controllata dal parametro $m$.
• Per i livelli di tipo Mersenne ($m = 2^k - 1$), la struttura diventa particolarmente semplice, agendo come una sequenza di Thue-Morse in base $B = 2^{2^k}$.

B. Soluzioni Generalizzate al Problema di Prouhet-Tarry-Escott (PTE)

Il lavoro estende il classico teorema di Prouhet.

• Per ogni livello $m$ e lunghezza dell'intervallo $N = B(m)^L$, la partizione indotta da $a_m$ su $\{0, \dots, N-1\}$ garantisce l'uguaglianza delle somme delle potenze fino al grado $s_m L - 1$, dove $s_m$ è il numero di posizioni di bit selezionate per periodo.
• Multi-livello: Combinando più livelli della torre (es. $(a_{m_1}, \dots, a_{m_k})$), si ottengono partizioni in $2^k$ classi con proprietà PTE, offrendo nuove famiglie di soluzioni non "ideali" ma con gradi elevati controllati dai parametri della maschera.

C. Numeri Evil e Odiosi Generalizzati e Equazioni Funzionali

L'autore generalizza le identità di composizione note per i numeri evil/odiosi classici (Allouche et al.).

• Per la sequenza classica ($m=0$), le correzioni nelle composizioni sono costanti (0 o 1).
• Per le iterazioni $m > 0$, le correzioni diventano sequenze automatiche non banali ($c_m(n)$).
• Vengono stabilite equazioni funzionali precise per le composizioni $u_m(u_m(n))$, $u_m(v_m(n))$, ecc., che coinvolgono queste sequenze di correzione. Si nota una dicotomia fondamentale tra livelli pari e dispari di $m$.

D. Complessità dei Fattori (Factor Complexity)

Per i livelli di tipo Mersenne ($m = 2^k - 1$), viene determinata completamente la complessità dei fattori $p_{a_m}(n)$.

• Si dimostra un regime lineare iniziale esatto: $p_{a_m}(n) = 2n$ per $1 \le n \le B+1$.
• Viene fornita una formula a tratti esatta e gerarchica per $n$ maggiori, ottenuta analizzando la sequenza derivata $\Delta(n)$, che è un punto fisso di una sostituzione uniforme.
• Per i livelli non-Mersenne, la struttura è più complessa e una formula chiusa completa rimane un problema aperto.

E. Estensioni Oltre l'Impostazione Dyadica

• Base $d$: La costruzione PTE viene generalizzata a basi arbitrarie $d$, mantenendo la struttura di maschera binaria sulle posizioni delle cifre.
• Sequenza Meta-Thue-Morse: Viene mostrato che la trasformata funziona anche su sequenze non classiche come la sequenza Meta-Thue-Morse ($M_2$), generando nuove famiglie PTE.
• Analogo Fibonacci: Viene esplorata l'applicazione della trasformata alla sequenza di Thue-Morse-Fibonacci (basata sulla numerazione di Zeckendorf). Sebbene non si ottenga una torre con la stessa struttura esplicita dyadica, emergono "ombre" PTE con difetti di grado 1 e 2 esprimibili tramite numeri di Fibonacci.

4. Significato e Impatto

Questo lavoro è significativo per diverse ragioni:

1. Unificazione: Fornisce una descrizione unificata e esplicita di una famiglia infinita di sequenze automatiche, collegando la trasformata di Thue-Morse a maschere binarie.
2. Nuove Soluzioni PTE: Estende notevolmente il panorama delle soluzioni al problema di Prouhet-Tarry-Escott, offrendo un meccanismo iterativo che controlla sia il grado di uguaglianza delle somme che il numero di classi.
3. Arricchimento Aritmetico: Rivela che l'iterazione di trasformazioni semplici su sequenze automatiche genera strutture aritmetiche ricche (sequenze di correzione automatiche), andando oltre i casi classici a correzione costante.
4. Apertura di Nuove Direzioni: Solleva problemi aperti sulla complessità delle sequenze non-Mersenne e sulla possibilità di costruire torri simili partendo da semi (seed) diversi (es. sequenze Sturmiane o Fibonacci), suggerendo una teoria più ampia delle "orbite di trasformata Thue-Morse".

In sintesi, Cloitre trasforma un'osservazione operativa su una singola sequenza in una teoria strutturata di sequenze automatiche, con profonde implicazioni nella teoria dei numeri, nella combinatoria delle parole e nella risoluzione di problemi di uguaglianza di somme di potenze.