Mahler equations for Zeckendorf numeration

Titolo: Equazioni di Mahler per la Numerazione di Zeckendorf

1. Il Problema e il Contesto

Il lavoro si inserisce nel campo della teoria dei numeri, della teoria degli automi e dell'algebra formale. L'obiettivo principale è estendere il teorema di Christol e i risultati di Becker e Dumas, che collegano la regolarità delle sequenze (generata da automi) all'algebraicità delle serie formali (soluzioni di equazioni di Mahler), dai sistemi di numerazione in base $k$ ai sistemi di numerazione di Pisot, in particolare alla numerazione di Zeckendorf.

• Contesto Esistente: Il teorema di Christol caratterizza le serie algebriche su campi finiti come quelle i cui coefficienti sono calcolabili da automi finiti deterministici leggendo la rappresentazione in base $p$ (sequenze $p$-automatiche). La nozione di regolarità (introdotta da Allouche e Shallit) generalizza questo concetto a sequenze su anelli commutativi, generando da automi pesati. Becker e Dumas hanno dimostrato che per una base $k \ge 2$, le sequenze $k$-regolari sono soluzioni di equazioni $k$-di Mahler e viceversa (per equazioni "isolanti").
• La Sfida: Estendere questi risultati alla numerazione di Zeckendorf (basata sui numeri di Fibonacci), dove la rappresentazione di un intero $n$ è unica e non contiene due 1 consecutivi. A differenza della base $k$, l'operazione di moltiplicazione per $k$ (aggiunta di uno zero) non corrisponde a un'operazione lineare semplice in Zeckendorf. In particolare, la mappa $n \mapsto kn$ è sostituita da una funzione $\phi$ che non è lineare, rendendo inapplicabili gli strumenti standard come gli operatori di Cartier usati nelle dimostrazioni classiche.

2. Metodologia

Gli autori adottano un approccio costruttivo basato su automi pesati e operatori lineari su serie formali.

• Definizione dell'Operatore $\Phi$: Viene introdotto un operatore lineare $\Phi: R[[x]] \to R[[x]]$ definito da $\Phi(\sum f_n x^n) = \sum f_n x^{\phi(n)}$, dove $\phi(n)$ è l'analogo Zeckendorf della moltiplicazione per la base. La funzione $\phi$ è definita spostando le cifre nella rappresentazione di Zeckendorf (es. se $n = \sum b_i F_i$, allora $\phi(n) = \sum b_i F_{i+1}$).
• Analisi della Non-Linearità: Poiché $\phi$ non è lineare ($\phi(m+n) \neq \phi(m) + \phi(n)$ in generale), gli autori definiscono un "difetto di linearità" $\delta(m, n) = \phi(m+n) - \phi(m) - \phi(n)$. Dimostrano che $\delta(m, n) \in \{-1, 0, 1\}$ e, crucialmente, che questo difetto può essere calcolato da un automa deterministico.
• Costruzione dell'Automa Universale:
  • Per le basi $k$, costruiscono un "automa pesato universale" che genera la soluzione di qualsiasi equazione di Mahler isolante $k$-di Mahler. Questo fornisce una nuova prova del teorema di Christol senza usare operatori di Cartier.
  • Per la numerazione di Zeckendorf, combinano l'automa universale con l'automa che calcola il difetto di linearità $\delta$. Lo stato dell'automa risultante include non solo gli indici della serie, ma anche una "finestra" di cifre e lo stato dell'automa che traccia il difetto di linearità.

3. Contributi Chiave

1. Definizione delle Equazioni Z-Mahler: Introducono formalmente le equazioni di Mahler adattate alla numerazione di Zeckendorf (Z-Mahler), della forma $P(x, y) = \sum A_i(x) \Phi^i(y) = 0$.
2. Costruzione Diretta di Automi: Forniscono una costruzione esplicita di un automa pesato che genera i coefficienti della soluzione di un'equazione Z-Mahler isolante. Questa costruzione evita gli operatori di Cartier, che non possiedono le proprietà necessarie nel contesto Zeckendorf.
3. Teorema di Esistenza (Teorema 1 e 29): Dimostrano che se una serie è soluzione di un'equazione Z-Mahler isolante (dove il coefficiente del termine di ordine zero è 1), allora la sequenza dei suoi coefficienti è Z-regolare (generata da un automa pesato).
4. Universalità: Mostrano che tutte le sequenze Z-regolari possono essere ottenute istanziando un unico "automa pesato universale" Z, generalizzando il risultato per le basi $k$.
5. Controesempio per Equazioni Non Isolanti: Forniscono un esempio (Proposizione 38) di un'equazione Z-Mahler non isolante la cui soluzione non è Z-regolare, dimostrando che la condizione di "isolamento" è necessaria.

4. Risultati Principali

• Teorema 1 (Equivalenza Parziale): Sia $R$ un anello commutativo. Se $f(x)$ è una soluzione di un'equazione Z-Mahler isolante $P(x, f(x)) = 0$, allora esiste un automa pesato Z che genera $f$.
• Teorema 2 (Automa Universale per Base $k$): Esiste un automa pesato universale tale che, fissati i coefficienti di un'equazione $k$-Mahler isolante e una condizione iniziale, l'automa istanziato genera la soluzione. Questo offre una nuova dimostrazione del teorema di Christol per $R = \mathbb{F}_q$.
• Stima della Complessità: Gli autori stimano il numero di stati dell'automa generato. Per le equazioni Z-Mahler, il numero di stati è limitato da una funzione che dipende dal grado dell'equazione ($d$), dall'altezza ($h$) e dal rapporto aureo $\phi$ (a causa della necessità di memorizzare il difetto di linearità). La complessità è dell'ordine di $O(d \cdot h^2 \cdot \phi^h)$.
• Regolarità delle Serie Z: Dimostrano che ogni serie Z-regolare è soluzione di un'equazione Z-Mahler (Corollario 34), chiudendo il cerchio per le equazioni isolanti.
• Crescita dei Coefficienti: Dimostrano che soluzioni di certe equazioni non isolanti (es. $(1-x)f(x) = \Phi(f(x))$) hanno coefficienti che crescono troppo rapidamente (super-polinomialmente) per essere Z-regolari, violando i limiti di crescita noti per le sequenze regolari.

5. Significato e Implicazioni

• Generalizzazione del Teorema di Christol: Il lavoro estende il ponte tra computabilità finita (automi) e algebraicità (equazioni funzionali) dai sistemi di numerazione posizionali standard ai sistemi di numerazione di Pisot, un passo significativo verso una teoria unificata delle sequenze automatiche e regolari.
• Nuovi Strumenti Algebrici: L'introduzione dell'operatore $\Phi$ basato su $\phi$ e la gestione esplicita del difetto di linearità tramite automi offrono nuovi strumenti per analizzare serie formali in contesti non standard.
• Applicazioni Teoriche: I risultati potrebbero avere implicazioni nello studio dei numeri trascendenti (metodo di Mahler) e nella teoria dei tilings (tassellazioni) e dei sistemi dinamici associati alle sostituzioni di Pisot, come accennato nell'introduzione riguardo ai "model sets".
• Problemi Aperti: Gli autori lasciano aperta la questione della caratterizzazione completa delle sequenze Z-regolari (inclusi i casi non isolanti) e l'estensione dei risultati di Cobham (sequenze che sono sia $k$- che $l$-Mahler) al caso misto $k$-Zeckendorf.

In sintesi, il paper risolve un problema tecnico complesso legato alla non-linearità della numerazione di Zeckendorf, fornendo una costruzione algoritmica robusta che collega equazioni funzionali generalizzate alla teoria degli automi pesati.