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 \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 $(a_i)_{i≥0}$, si costruisce una matrice infinita $A = (a_{k,\ell})_{k,\ell≥0}$, dove $a_{k,\ell} = a_{k+\ell}$. Per una sottomatrice $m \times n$ $A(i,m,n)$, la somma di tutti gli elementi è: $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)$, tutti i valori $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)$ è 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)$ (Proposizione 6)
5. Estensione Tribonacci: Esamina problemi analoghi per la parola Tribonacci (Teorema 10)

Spiegazione dei Metodi

Definizione del Compito

Data una sequenza infinita $(a_i)_{i≥0}$, si costruisce una matrice di Hankel: $A(i,m,n) := \begin{pmatrix} 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.