Balanced Fibonacci word rectangles, and beyond

Titolo: Parallelogrammi Bilanciati della Parola di Fibonacci e Oltre

1. Il Problema

Il lavoro si concentra sulle proprietà di "bilanciamento" (balance) delle matrici rettangolari derivate da parole infinite su un alfabeto binario (o multilingue).

• Definizione: Data una sequenza infinita $(a_i)_{i \ge 0}$, si definisce una matrice infinita $A$ dove l'elemento $a_{k,\ell} = a_{k+\ell}$. Le sottomatrici $m \times n$ di questa matrice, denotate come $A(i, m, n)$, rappresentano finestre scorrevoli della sequenza originale.
• Bilanciamento: Una coppia di dimensioni $(m, n)$ è detta bilanciata se, per tutte le possibili posizioni $i$ della finestra, il numero totale di occorrenze di ciascun simbolo (o la somma degli elementi nel caso binario) nelle sottomatrici $A(i, m, n)$ assume al massimo due valori distinti.
• Obiettivo: Determinare quali coppie $(m, n)$ soddisfano questa proprietà di bilanciamento per diverse parole infinite famose, in particolare la Parola di Fibonacci, la Parola di Tribonacci e la Parola di Thue-Morse.

2. Metodologia

Gli autori adottano un approccio basato sulla teoria degli automi finiti e sulla logica del primo ordine, implementato tramite il software open-source Walnut.

• Automata e Numerazione: Per le parole Sturmiane (come quella di Fibonacci), che sono associate a numeri irrazionali quadratici, utilizzano il sistema di numerazione di Ostrowski (o il sistema di Zeckendorf per la Fibonacci). Questo permette di rappresentare gli indici $m$ e $n$ in modo tale che le proprietà aritmetiche possano essere decise da automi finiti.
• Criterio di Bilanciamento:
  • Per le parole Sturmiane, dimostrano che il bilanciamento dipende dalla differenza $\Delta(i, m, n) = T(i+1, m, n) - T(i, m, n)$, dove $T$ è la somma degli elementi. Il criterio di bilanciamento è soddisfatto se e solo se la sequenza delle differenze non contiene blocchi del tipo $1, 0, \dots, 0, 1$ o $-1, 0, \dots, 0, -1$.
  • Questo criterio è esprimibile come una formula logica del primo ordine. Utilizzando i risultati di [16] e [9], trasformano tale formula in un automa finito che accetta esattamente le coppie $(m, n)$ bilanciate.
• Implementazione Walnut: Gli autori scrivono codice specifico in Walnut per:
  1. Definire le parole (es. Fibonacci, Tribonacci).
  2. Calcolare le somme parziali e le differenze.
  3. Verificare la condizione di assenza di blocchi critici.
  4. Generare automi che decidono il bilanciamento.
• Rappresentazioni Lineari: Per analizzare la densità dei valori distinti (Teorema 8), utilizzano rappresentazioni lineari (vettori e matrici) per calcolare funzioni complesse su grandi numeri, verificando identità tramite programmi Maple.

3. Risultati Chiave

A. Parola di Fibonacci

• Caratterizzazione Esatta: Gli autori costruiscono un automa a 15 stati (Figura 1) che accetta esattamente le coppie $(m, n)$ bilanciate per la parola di Fibonacci.
• Conferma di Risultati Precedenti: Dimostrano automaticamente il teorema di Anselmo et al., che afferma che se $\max(m, n)$ è un numero di Fibonacci, allora la coppia è bilanciata.
• Nuove Proprietà:
  • Proposizione 5: Stabiliscono relazioni di simmetria e periodicità per le coppie bilanciate all'interno di intervalli definiti dai numeri di Fibonacci (es. $(F_{n+1} + i, j)$ è bilanciata se e solo se $(F_{n+2} - i, j)$ lo è).
  • Densità: Dimostrano che la densità delle $n$ per cui $(m, n)$ è bilanciata è limitata inferiormente da circa $1/\phi^m$.
• Parallelogrammi Diversi: Mostrano che per $m=n=F_{3k/2}$, il numero di valori distinti della somma $T(i, m, n)$ cresce linearmente con $k$ ($\Theta(k)$), dimostrando che non tutte le matrici quadrate di grandi dimensioni sono bilanciate.

B. Parola di Tribonacci

• Risultato Principale (Teorema 10):
  • Se $m=1$, tutte le matrici sono 2-bilanciate (ereditando la proprietà dalla parola stessa).
  • Se $m=2$, esiste un automa a 77 stati che caratterizza le $n$ bilanciate. La lista inizia con $1, 2, 3, 4, 7, 8, \dots$ e non sembra ammettere una descrizione semplice in linguaggio naturale.
  • Se $m \ge 3$, non esistono valori di $n$ per cui le matrici $m \times n$ siano 2-bilanciate. La prova si basa sulla costruzione di due rettangoli che differiscono per almeno 3 occorrenze del simbolo '2' in una sotto-matrice $3 \times 3$.

C. Parola di Thue-Morse

• Analisi Completa: A differenza delle altre parole, per la Thue-Morse è possibile ottenere una descrizione completa e precisa del bilanciamento.
• Teorema 11: Dimostrano che per ogni rettangolo $m \times n$, la quantità $|2 \cdot |A(i, m, n)|_1 - mn|$ è limitata da 4. Il bilanciamento è sempre 1, 2, 3 o 4.
• Automazione Complessa: Costruiscono un automa a 92 stati che, dato $m$ e $n$ in base 2, determina il bilanciamento esatto.
  • Nota tecnica: Questo calcolo è stato estremamente oneroso, richiedendo un automa intermedio di oltre 32 milioni di stati, 12.834 secondi di CPU e 100 GB di RAM.
• Teorema 14: Per $m, n \ge 3$, il bilanciamento è esattamente 3 se e solo se sia $m$ che $n$ sono dispari.

4. Contributi e Significato

1. Generalizzazione del Bilanciamento: Il lavoro estende il concetto di bilanciamento da parole lineari (ben studiato) a strutture bidimensionali (rettangoli), fornendo un quadro teorico unificato.
2. Potere Computazionale degli Automi: Dimostra che problemi apparentemente complessi sulla struttura delle parole infinite (come la caratterizzazione esatta di coppie $(m, n)$ bilanciate) possono essere risolti in modo algoritmico e automatico utilizzando automi finiti e logica del primo ordine.
3. Strumenti Pratici: Fornisce codici Walnut concreti e verificabili per la comunità scientifica, permettendo ad altri ricercatori di esplorare proprietà simili per altre parole o parametri.
4. Risultati Negativi e Positivi:
   • Per la parola di Fibonacci, offre una caratterizzazione completa.
   • Per la Tribonacci, stabilisce un limite rigido: il bilanciamento è impossibile per rettangoli "spessi" ($m \ge 3$).
   • Per la Thue-Morse, risolve completamente il problema, mostrando una struttura di bilanciamento molto più ricca e prevedibile rispetto alle parole Sturmiane.

In sintesi, il paper rappresenta un avanzamento significativo nella teoria combinatoria delle parole, dimostrando come l'automazione logica possa svelare proprietà profonde e non ovvie di strutture matematiche classiche.