2025-11-10T03:15:48.044021

Balanced Fibonacci word rectangles, and beyond

Shallit, Vukusic
Following a recent paper of Anselmo et al., we consider $m \times n$ rectangular matrices formed from the Fibonacci word, and we show that their balance properties can be solved with a finite automaton. We also generalize the result to every Sturmian characteristic word corresponding to a quadratic irrational. Finally, we also examine the analogous question for the Tribonacci word.
academic

Rettangoli di parole Fibonacci equilibrate, e oltre

Informazioni Fondamentali

  • ID Articolo: 2509.25994
  • Titolo: Balanced Fibonacci word rectangles, and beyond
  • Autori: Jeffrey Shallit (University of Waterloo), Ingrid Vukusic (University of York)
  • Classificazione: math.NT cs.DM cs.FL math.CO
  • Data di Pubblicazione: 15 ottobre 2025 (Preprint ArXiv)
  • Link Articolo: https://arxiv.org/abs/2509.25994

Riassunto

Questo articolo, basato su ricerche recenti di Anselmo e altri, considera matrici rettangolari m×nm \times n formate da parole Fibonacci, dimostrando che le loro proprietà di equilibrio possono essere risolte mediante automi finiti. La ricerca generalizza ulteriormente i risultati a ogni parola caratteristica Sturmiana corrispondente a numeri irrazionali quadratici, e esamina problemi analoghi per la parola Tribonacci.

Contesto di Ricerca e Motivazione

Definizione del Problema

Il problema centrale di questo articolo è l'equilibrio delle matrici di parole: data una sequenza infinita (ai)i≥0(a_i)_{i≥0}, si costruisce una matrice infinita A=(ak,ℓ)k,ℓ≥0A = (a_{k,\ell})_{k,\ell≥0}, dove ak,ℓ=ak+ℓa_{k,\ell} = a_{k+\ell}. Per una sottomatrice m×nm \times n A(i,m,n)A(i,m,n), la somma di tutti gli elementi è: T(i,m,n):=∑k=0m−1∑ℓ=0n−1ai+k+ℓT(i,m,n) := \sum_{k=0}^{m-1}\sum_{\ell=0}^{n-1} a_{i+k+\ell}

Il problema di equilibrio è: per quali coppie (m,n)(m,n), tutti i valori T(i,m,n)T(i,m,n) assumono al massimo due valori distinti?

Motivazione della Ricerca

  1. Importanza Teorica: La parola Fibonacci è un oggetto classico della matematica combinatoria, le cui proprietà di equilibrio sono strettamente correlate alla teoria dei numeri e alla teoria degli automi
  2. Limitazioni Esistenti: Anselmo e altri hanno provato che i rettangoli sono equilibrati quando max⁡(m,n)\max(m,n) è un numero Fibonacci, ma una caratterizzazione completa rimane assente
  3. Innovazione Metodologica: L'uso di automi finiti per risolvere questo tipo di problemi fornisce nuovi strumenti computazionali

Contributi Principali

  1. Caratterizzazione Completa: Fornisce una caratterizzazione completa mediante automi della proprietà di equilibrio dei rettangoli di parole Fibonacci (Teorema 2 e Corollario 3)
  2. Risultati Generalizzati: Estende i risultati a tutte le parole Sturmiane corrispondenti a numeri irrazionali quadratici (Teorema 2)
  3. Implementazione Algoritmica: Fornisce implementazioni concrete e verifiche basate sul software Walnut
  4. Risultati di Densità: Dimostra proprietà di densità delle coppie equilibrate (m,n)(m,n) (Proposizione 6)
  5. Estensione Tribonacci: Esamina problemi analoghi per la parola Tribonacci (Teorema 10)

Spiegazione dei Metodi

Definizione del Compito

Data una sequenza infinita (ai)i≥0(a_i)_{i≥0}, si costruisce una matrice di Hankel:

a_i & a_{i+1} & \cdots & a_{i+n-1} \\ a_{i+1} & a_{i+2} & \cdots & a_{i+n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{i+m-1} & a_{i+m} & \cdots & a_{i+m+n-2} \end{pmatrix}$$ Obiettivo: Determinare quali coppie $(m,n)$ rendono tutti i valori $T(i,m,n)$ con al massimo due valori distinti. ### Quadro Teorico Centrale #### Proprietà delle Parole Sturmiane Per le parole Sturmiane, si definisce $\Delta(i,m,n) := T(i+1,m,n) - T(i,m,n)$, con: $$\Delta(i,m,n) \in \{-1, 0, 1\}$$ **Lemma Chiave 1**: $(m,n)$ è equilibrato se e solo se la sequenza $(\Delta(i,m,n))_{i≥0}$ non contiene blocchi della forma $1,0,0,\ldots,0,1$ o $-1,0,0,\ldots,0,-1$. #### Metodo degli Automi Per un numero irrazionale quadratico $\alpha$, esiste un automa finito $M$ che, dato in input la rappresentazione $\alpha$-adica di Ostrowski di $n$ e $x$, accetta se e solo se $x = \lfloor n\alpha \rfloor$. **Teorema Principale 2**: Esiste un algoritmo che, dato un numero irrazionale quadratico $\alpha \in (0,1)$, costruisce un automa finito che, dato in input la rappresentazione $\alpha$-adica di Ostrowski della coppia $(m,n)$, accetta se e solo se il blocco $m \times n$ è equilibrato. ### Punti di Innovazione Tecnica 1. **Implementazione Automatica del Criterio di Equilibrio**: Converte le condizioni del Lemma 1 in una formula logica del primo ordine, poi in un automa 2. **Gestione della Rappresentazione di Zeckendorf**: Affronta abilmente il problema dei numeri negativi, utilizzando $T(i+1,m,n) - T(i,m,n) + 1 \in \{0,1,2\}$ 3. **Implementazione Walnut**: Fornisce un'implementazione completa del codice, generando un automa con 15 stati ## Configurazione Sperimentale ### Strumenti e Implementazione - **Software Walnut**: Strumento specializzato per la costruzione e verifica di automi - **Rappresentazione di Zeckendorf**: Sistema di rappresentazione standard per numeri Fibonacci - **Rappresentazione Tribonacci**: Utilizzata per l'analisi della parola Tribonacci ### Metodi di Verifica 1. **Costruzione dell'Automa**: Generazione dell'automa bal mediante Walnut (15 stati) 2. **Verifica dei Teoremi**: Verifica dei risultati di Anselmo e altri come casi particolari 3. **Analisi di Densità**: Calcolo delle proprietà di distribuzione delle coppie equilibrate ## Risultati Sperimentali ### Risultati Principali per le Parole Fibonacci **Corollario 3**: L'automa con 15 stati in Figura 1 risolve completamente il problema di equilibrio per i rettangoli di parole Fibonacci. **Corollario 4**: Verifica il teorema di Anselmo e altri: se $\max(m,n)$ è un numero Fibonacci, allora la matrice $m \times n$ è equilibrata. ### Proprietà Strutturali **Proposizione 5**: Per $n ≥ 2$: - $(i,j)$ è equilibrato se e solo se $(i',j)$ è equilibrato, dove $F_{n+1} < i,i' < F_{n+2}$ e $j ≥ F_{n-1}$ - $(F_{n+1}+i,j)$ è equilibrato se e solo se $(F_{n+2}-i,j)$ è equilibrato **Proposizione 6** (Risultato di Densità): Se $F_i < m ≤ F_{i+1}$, allora per ogni $n ≥ 1$ esiste $j$, $1 ≤ j ≤ F_{i+1}$ tale che $(m,n+j)$ sia equilibrato. ### Risultati di Varietà **Teorema 8**: Per $m = n = F_{3k}/2$, il numero di valori distinti di $T(i,m,n)$ è almeno $k+1$. **Corollario 9**: Il numero di valori distinti di $T(i,F_{3n}/2,F_{3n}/2)$ è $\Theta(n)$. ### Risultati per la Parola Tribonacci **Teorema 10**: Assumendo $m ≤ n$: - Se $m = 1$, tutti i rettangoli $m \times n$ sono 2-equilibrati - Se $m = 2$, esiste un automa con 77 stati che accetta tutti gli $n$ per cui il rettangolo $m \times n$ è 2-equilibrato - Se $m ≥ 3$, non esiste alcun $n$ che renda il rettangolo $m \times n$ 2-equilibrato ## Lavori Correlati 1. **Teoria delle Parole Sturmiane**: Costruita sui lavori classici di Berstel, Brown e altri 2. **Ricerca sull'Equilibrio**: Estende la ricerca di Vuillon e altri sull'equilibrio delle parole 3. **Metodo degli Automi**: Utilizza la teoria degli insiemi p-riconoscibili di Bruyère e altri 4. **Proprietà delle Parole Fibonacci**: Basata su ampia ricerca esistente sulle parole Fibonacci ## Conclusioni e Discussione ### Conclusioni Principali 1. Risolve completamente il problema di equilibrio per i rettangoli di parole Fibonacci, fornendo una caratterizzazione mediante automa con 15 stati 2. Il metodo è generalizzabile a tutte le parole Sturmiane corrispondenti a numeri irrazionali quadratici 3. Il caso della parola Tribonacci è più complesso, richiedendo un automa con 77 stati per il caso $m=2$ ### Limitazioni 1. Il metodo è applicabile solo alle parole Sturmiane corrispondenti a numeri irrazionali quadratici 2. La caratterizzazione completa della parola Tribonacci rimane complessa 3. I casi di ordine superiore (come Tribonacci con $m≥3$) potrebbero non avere soluzione ### Direzioni Future 1. Generalizzazione a parole morphic più generali 2. Studio di casi ad alta dimensionalità 3. Ottimizzazione del numero di stati dell'automa ## Valutazione Approfondita ### Punti di Forza 1. **Completezza Teorica**: Fornisce una soluzione completa al problema di equilibrio per le parole Fibonacci 2. **Innovazione Metodologica**: Combina abilmente la teoria degli automi e la matematica combinatoria 3. **Forte Praticità**: Fornisce implementazioni algoritmiche concrete e strumenti di verifica 4. **Risultati Profondi**: Rivela i legami più profondi tra l'equilibrio e le proprietà della teoria dei numeri ### Carenze 1. **Complessità**: Sebbene il metodo degli automi sia completo, potrebbe non essere sufficientemente intuitivo 2. **Limitazioni di Generalizzazione**: Applicabile solo a tipi specifici di numeri irrazionali 3. **Complessità Computazionale**: Non analizza in dettaglio la complessità temporale dell'automa ### Impatto 1. **Contributo Teorico**: Fornisce nuove prospettive per la ricerca interdisciplinare tra matematica combinatoria e teoria degli automi 2. **Valore Pratico**: L'implementazione Walnut rende i risultati verificabili ed estensibili 3. **Significato Metodologico**: Dimostra come utilizzare gli automi per risolvere problemi combinatori complessi ### Scenari di Applicazione 1. Ricerca sull'equilibrio nella matematica combinatoria 2. Applicazioni della teoria degli automi 3. Studio delle proprietà dei numeri irrazionali nella teoria dei numeri 4. Problemi decisionali nella progettazione di algoritmi ## Bibliografia L'articolo cita 19 importanti riferimenti, principalmente includenti: - Opere classiche di Allouche & Shallit sulle sequenze automatiche - Lavori fondamentali di Berstel su parole Fibonacci e parole Sturmiane - Ricerche recenti correlate di Anselmo e altri - Letteratura correlata sulla teoria degli automi e la teoria dei numeri --- Questo articolo trova un eccellente equilibrio tra profondità teorica e praticità, non solo risolvendo un problema combinatorio specifico, ma anche dimostrando la potenza del metodo degli automi nel trattare questo tipo di problemi. L'implementazione completa e la verifica conferiscono ai risultati un'elevata credibilità e valore pratico.