Infinite Words with very Low Factor Complexity: an introduction to Combinatorics on Words

Queste note di lezione introducono la combinatoria sulle parole concentrandosi sulla complessità fattoriale bassa delle parole infinite, esplorando la loro minimizzazione, formalizzazione e caratterizzazione attraverso strumenti classici come le parole di Sturmian e i grafi di Rauzy, e presentando una nuova dimostrazione algebrica di un teorema di Tijdeman che generalizza un risultato fondamentale di Morse e Hedlund.

L'essenziale

Ecco una spiegazione semplice e creativa di queste note di lezione, pensata per chiunque, anche senza una laurea in matematica.

Immagina di avere un infinito nastro di carta su cui sono scritti dei simboli (come lettere dell'alfabeto o numeri). Questo nastro non finisce mai. La domanda fondamentale di questo lavoro è: quanto è "complicato" questo nastro?

Per rispondere, gli autori usano un concetto chiamato complessità dei fattori. Immagina di prendere un paio di forbici e tagliare dal nastro tutti i possibili pezzetti di una certa lunghezza (diciamo, 3 lettere).

• Se il nastro è AAAAA..., ci sarà solo un tipo di pezzetto di 3 lettere: AAA. La complessità è bassissima (1).
• Se il nastro è ABABAB..., avrai ABA e BAB. La complessità è 2.
• Se il nastro è caotico come il testo di un libro, avrai quasi tutti i possibili pezzetti di 3 lettere. La complessità è altissima.

Il Problema: Cosa rende un nastro "interessante"?

Nel mondo delle parole infinite, ci sono due estremi noiosi:

1. I nastro periodici: Come 123123123.... Si ripetono all'infinito. Sono prevedibili, noiosi e la loro complessità è molto bassa.
2. I nastro casuali: Come il lancio di una moneta infinita. Sono imprevedibili, ma la loro complessità è altissima (esplode).

Gli autori si chiedono: Esiste qualcosa di "interessante" che non sia né noioso (periodico) né caotico? Qualcosa che sia ordinato ma non ripetitivo? E qual è il livello minimo di complessità che un nastro "interessante" può avere?

Capitolo 1: I "Fratelli Gemelli" del Numero d'Oro (Parole Sturmiane)

Per i nastri fatti con solo due simboli (binari, come 0 e 1), la risposta è stata trovata decenni fa. Esiste una classe speciale di nastri chiamati Parole Sturmiane.

• La loro magia: Hanno la complessità più bassa possibile per non essere periodici. Se la lunghezza del pezzetto è $n$, la complessità è esattamente $n+1$.
• L'analogia: Immagina di camminare su una griglia quadrata (come una scacchiera) partendo dall'angolo in basso a sinistra e andando verso l'alto a destra. Se il tuo percorso è una linea retta con una pendenza "strana" (un numero irrazionale, come il rapporto aureo $\phi$), il modo in cui la linea attraversa le linee della griglia crea una sequenza di passi (su o destra) che forma una Parola Sturmiana.
• Il segreto: Queste parole sono legate ai numeri irrazionali. Se la pendenza della tua linea è un numero "normale" (come 1/2), il nastro diventa periodico (noioso). Se è un numero "strano" (irrazionale), il nastro è Sturmiano (interessante e minimamente complesso).

Capitolo 2: Cosa succede se abbiamo più simboli? (Alfabeti Ternari, Quaternari...)

Qui la storia si fa più complessa. Se usiamo 3 lettere (A, B, C) invece di 2, la definizione di "interessante" cambia.

• Non basta dire "non deve ripetersi". Potremmo creare nastri che non si ripetono ma sono comunque "finti" (costruiti artificialmente attaccando pezzi di parole Sturmiane).
• Gli autori introducono un nuovo filtro: l'indipendenza razionale delle frequenze.
  • Immagina di contare quante volte appare la A, la B e la C. Se il rapporto tra questi numeri è "semplice" (es. 1:1:1 o 2:1:1), il nastro è ancora un po' "banale".
  • Se i rapporti sono "strani" (irrazionali e indipendenti tra loro), allora il nastro è davvero interessante.
• La scoperta di Tijdeman (1999): R. Tijdeman ha scoperto che per un nastro con $d$ simboli e frequenze "strane", la complessità minima non è più $n+1$, ma $(d-1)n + 1$.
  • Con 2 simboli: $1n + 1$.
  • Con 3 simboli: $2n + 1$.
  • Con 4 simboli: $3n + 1$.
    È come se ogni simbolo aggiuntivo richiedesse un po' più di "spazio" per essere interessante senza diventare caotico.

Capitolo 3: La Nuova Prova (L'Approccio Matematico)

Il terzo capitolo è il cuore tecnico del lavoro. Gli autori (Andrieu e Cassaigne) hanno trovato un modo nuovo e più elegante per dimostrare il teorema di Tijdeman.

• Il vecchio metodo: Era basato su un ragionamento combinatorio (contare e incollare pezzi di parole), un po' come risolvere un puzzle pezzo per pezzo.
• Il nuovo metodo: Usano l'algebra lineare (la matematica delle matrici e dei vettori).
  • Immagina di costruire una mappa del traffico (un grafo) dove i nodi sono i pezzetti di parole e le strade sono le transizioni.
  • Costruiscono una Matrice di Flusso (Flow Matrix). Pensa a questa matrice come a un sistema di tubi idraulici o circuiti elettrici. Ogni "pezzo" di parola è un nodo, e il flusso è la frequenza con cui appare.
  • Usano una legge fisica (la legge di Kirchhoff, che dice che l'acqua che entra in un nodo deve uscire) per dimostrare che se la complessità fosse troppo bassa, il sistema idraulico collasserebbe o richiederebbe che i numeri siano "semplici" (razionali), violando la nostra regola di "interesse".
• Il risultato extra: Questo nuovo metodo ha rivelato che tutte queste parole "perfette" (con complessità minima e frequenze strane) hanno una struttura speciale chiamata dendrica.
  • L'analogia dell'albero: "Dendrico" viene da dendron (albero). Significa che se guardi come una parola può essere estesa a sinistra e a destra, le possibilità si diramano come i rami di un albero, senza creare cicli o incroci confusi. È una struttura pulita, organica e ramificata.

In Sintesi

Questo documento è una guida che ci porta da una domanda semplice ("Quanto è complicato un nastro infinito?") fino a una risposta profonda:

1. Esiste un limite minimo di complessità per essere interessanti.
2. Per essere davvero interessanti, le frequenze dei simboli devono essere "strane" (irrazionali).
3. Esiste una formula precisa per questo limite minimo.
4. Le parole che raggiungono questo limite hanno una struttura interna bellissima e ramificata (come alberi), che può essere studiata non solo contando, ma usando la potenza dell'algebra e dei circuiti elettrici.

È un viaggio che mostra come la matematica trovi ordine e bellezza anche nel caos apparente delle sequenze infinite.

Sommario tecnico

Ecco una sintesi tecnica dettagliata del documento "Infinite Words with very Low Factor Complexity: an introduction to Combinatorics on Words" di Mélodie Andrieu, basata sul contenuto fornito.

Panoramica Generale

Queste note di lezione introducono la combinatoria sulle parole infinite, focalizzandosi sull'interazione con la dinamica, l'algebra e l'aritmetica. Il tema centrale è la complessità dei fattori (il numero di sotto-parole distinte di lunghezza $n$) per parole infinite su alfabeti finiti. L'obiettivo è caratterizzare le parole che raggiungono la complessità minima possibile, distinguendo tra casi "banali" (periodici) e "interessanti" (non periodici o con proprietà aritmetiche specifiche).

Il testo è strutturato in tre capitoli:

1. Il caso binario e il teorema di Morse-Hedlund (1938).
2. La generalizzazione ad alfabeti $d$-ari ($d \ge 3$) e il teorema di Tijdeman (1999).
3. Una nuova dimostrazione algebrica del teorema di Tijdeman e le sue conseguenze strutturali (2022).

---

1. Il Problema e il Contesto

Definizione di Complessità:
Data una parola infinita $w$ su un alfabeto di dimensione $d$, la funzione di complessità $p_w(n)$ conta il numero di fattori distinti di lunghezza $n$.

• Le parole periodicamente hanno complessità limitata.
• Il teorema di Morse-Hedlund (1938) stabilisce che una parola è eventualmente periodica se e solo se $p_w(n) \le n$ per qualche $n$. Di conseguenza, per una parola non periodica, $p_w(n) \ge n+1$.

La Domanda Centrale:
Qual è la complessità minima per una parola "interessante" su un alfabeto di dimensione $d \ge 3$?

• Per $d=2$, le parole con complessità $n+1$ sono le parole di Sturmian. Sono caratterizzate da frequenze delle lettere irrazionali e indipendenti razionalmente.
• Per $d \ge 3$, la semplice condizione di "non periodicità" non è sufficiente: esistono parole non periodiche con complessità lineare bassa ($n+d-1$) che sono però costruzioni artificiali di parole di Sturmian (es. prefissate con lettere che non ricorrono).
• Nuova Condizione: Per generalizzare correttamente il concetto di "non banalità" ad alfabeti arbitrari, si richiede l'indipendenza razionale delle frequenze delle lettere. Cioè, le frequenze $f_1, \dots, f_d$ devono generare uno spazio vettoriale su $\mathbb{Q}$ di dimensione $d$.

---

2. Metodologia e Strumenti

Il documento utilizza un approccio ibrido che combina:

• Combinatoria sulle parole: Analisi dei fattori, fattori speciali (destra/sinistra), e grafi di Rauzy.
• Teoria dei Numeri e Dinamica: Connessione con le frazioni continue, rotazioni del cerchio, flussi lineari sul toro e sistemi dinamici minimi.
• Algebra Lineare: Introduzione del concetto di matrice di flusso (flow matrix) per analizzare le relazioni lineari tra le frequenze dei fattori.

Strumenti Chiave:

1. Grafi di Rauzy: Grafi diretti i cui nodi sono i fattori di lunghezza $n$ e gli archi sono i fattori di lunghezza $n+1$.
2. Matrici di Flusso ($M$): Una matrice rettangolare $M$ di dimensione $p_w(n) \times p_w(n+1)$ definita come differenza tra le matrici di estensione destra e sinistra. Gli elementi sono $1, -1, 0$ e rappresentano il flusso di probabilità tra i fattori.
3. Processo di Rinormalizzazione: Utilizzato nel caso binario per collegare le parole di Sturmian alle frazioni continue.

---

3. Risultati Chiave e Contributi

Capitolo 1: Il Caso Binario ($d=2$)

• Teorema di Morse-Hedlund: Conferma che la complessità minima per parole non periodiche è $n+1$.
• Parole di Sturmian: Sono esattamente le parole con complessità $n+1$.
  • Sono caratterizzate da frequenze delle lettere $f_1, f_2$ tali che $f_1/f_2$ è un numero irrazionale.
  • Esistono costruzioni efficaci tramite sostituzioni ($\sigma_1, \sigma_2$) legate alle frazioni continue.
  • Ammettono descrizioni dinamiche equivalenti: codifiche di rotazioni del cerchio, flussi su tori bidimensionali, e traiettorie di biliardi su tavole quadrate.

Capitolo 2: Generalizzazione a $d$-ari e il Teorema di Tijdeman

• Limite della non periodicità: Per $d \ge 3$, esistono parole non periodiche con complessità $n+d-1$ che non sono "interessanti" (es. parole quasi-Sturmian). Queste hanno frequenze delle lettere linearmente dipendenti su $\mathbb{Q}$ (dimensione dello spazio razionale = 2).
• Condizione di Indipendenza Razionale: Si propone di richiedere che le frequenze delle lettere siano razionalmente indipendenti (dimensione dello spazio = $d$).
• Teorema di Tijdeman (1999):
  • Se una parola $d$-aria ha frequenze delle lettere razionalmente indipendenti, allora la sua complessità soddisfa:
    $$p_w(n) \ge (d-1)n + 1$$
  • Esistono parole che raggiungono questo limite (es. parole di Arnoux-Rauzy, codifiche di scambi di intervalli).
• Versione Rafforzata (Andrieu-Cassaigne 2022):
  • Il teorema è stato generalizzato considerando il grado massimo di irrazionalità $\Delta_w$ (massima dimensione dello spazio generato dalle frequenze nei limiti di sub-sequenze).
  • La disuguaglianza diventa: $p_w(n) \ge (\Delta_w - 1)(n-1) + d$.

Capitolo 3: Nuova Dimostrazione Algebrica e Conseguenze

• Nuova Dimostrazione (2022): Andrieu e Cassaigne forniscono una prova puramente algebrica del teorema di Tijdeman (nella sua versione rafforzata) utilizzando l'algebra lineare applicata alle matrici di flusso.
  • Si studia il nucleo (kernel) della matrice di flusso $M$.
  • Si dimostra che se la complessità fosse troppo bassa, le frequenze dei fattori di lunghezza $n+1$ genererebbero uno spazio vettoriale razionale di dimensione troppo piccola, portando a una contraddizione con l'ipotesi di indipendenza razionale delle frequenze delle lettere.
• Risultato Strutturale (Teorema 3.2):
  • Tutte le parole infinite $d$-arie con frequenze razionalmente indipendenti e complessità minima $(d-1)n + 1$ sono parole dendriche.
  • Una parola è dendrica se il suo grafo di estensione per ogni fattore è un albero (connesso e aciclico).
  • Questo collega la complessità minima alla struttura combinatoria dei grafi di estensione, fornendo una caratterizzazione parziale delle parole ottimali per $d \ge 3$.

---

4. Significato e Impatto

1. Unificazione Teorica: Il lavoro collega profondamente la complessità combinatoria delle parole alla teoria dei numeri (indipendenza razionale) e alla dinamica simbolica.
2. Superamento del Caso Binario: Risolve il problema di come generalizzare il concetto di "parola complessa ma semplice" (Sturmian) ad alfabeti più grandi, identificando l'indipendenza razionale come la condizione corretta per escludere costruzioni patologiche.
3. Nuovi Strumenti Matematici: L'introduzione e l'uso sistematico delle matrici di flusso offrono un potente strumento algebrico per analizzare le proprietà asintotiche delle parole infinite, alternativo alle tecniche puramente combinatorie usate da Tijdeman.
4. Caratterizzazione Strutturale: Il risultato che le parole a complessità minima sono dendriche è un passo fondamentale verso la classificazione completa di queste parole per $d \ge 3$, un problema che rimane aperto nella sua totalità (caratterizzazione dinamica completa).
5. Rafforzamento dei Risultati: La dimostrazione del 2022 non solo riproduce il risultato di Tijdeman, ma lo estende a casi in cui le frequenze non sono ben definite (usando limiti di sub-sequenze) e utilizza il grado massimo di irrazionalità, fornendo un limite inferiore più stretto e generale.

In sintesi, queste note di lezione offrono una panoramica rigorosa e aggiornata su come la combinatoria delle parole possa essere utilizzata per studiare la complessità strutturale dei sistemi dinamici, ponendo le basi per nuove ricerche sulla classificazione delle parole a bassa complessità su alfabeti arbitrari.