Almost Golomb Sequences

1. Il Problema e il Contesto

Il lavoro si inserisce nello studio delle sequenze autoreferenziali di interi positivi. La sequenza di Golomb classica, indicata con $G(n)$ (OEIS A001462), è definita come l'unica sequenza non decrescente di interi positivi in cui l'intero $n$ appare esattamente $G(n)$ volte. Essa soddisfa la regola globale:
$$G\left( \sum_{k=1}^{n} G(k) \right) = n$$
Questa sequenza presenta una crescita asintotica regolare governata dal rapporto aureo $\phi$ ($G(n) \sim C n^{\phi-1}$) e non è $k$-regolare per alcun $k \ge 2$.

L'obiettivo del paper è introdurre e analizzare le "Quasi-Sequenze di Golomb" (o Almost Golomb sequences), ottenute modificando la regola di Golomb sostituendo la somma cumulativa infinita con una finestra scorrevole di dimensione fissa $r$. La nuova definizione è data da:
$$a\left( \sum_{j=0}^{r-1} a(n-j) \right) = n$$
dove $a(n)$ è il più piccolo intero $\ge a(n-1)$ che soddisfa l'equazione. Il problema centrale è comprendere come questa "truncazione" della memoria (da infinita a finita) alteri le proprietà strutturali, asintotiche e combinatorie della sequenza.

2. Metodologia

L'autore impiega una combinazione di tecniche analitiche, algebriche e computazionali:

• Costruzione Induttiva e Unicità: Viene dimostrato l'esistenza e l'unicità della sequenza per ogni $r \ge 2$ attraverso una costruzione induttiva basata sulla struttura delle "corse" (run) dei valori.
• Teoria delle Sequenze Automatiche e Regolari: Viene applicato il criterio di Allouche-Shallit per dimostrare che le sequenze sono $r$-regolari. Questo comporta la riduzione della sequenza delle differenze prime $d(n) = a(n+1) - a(n)$ a un automa finito deterministico (DFAO) che legge la rappresentazione in base $r$ di $n$.
• Denesting (Scomposizione Esplicita): Per i casi piccoli ($r \in \{2, 3, 4, 5\}$), l'autore deriva formule ricorsive esplicite (denesting) che esprimono $a(rn+i)$ in termini di $a(n)$ e sequenze di correzione binarie.
• Verifica Computazionale (Walnut): Per $r=4$ e $r=5$, le identità ricorsive complesse vengono identificate analiticamente e poi certificate rigorosamente utilizzando il teorema prover Walnut, che verifica le proprietà delle sequenze automatiche.
• Analisi Asintotica: Vengono studiati i limiti delle frazioni $a(n)/n$ lungo progressioni geometriche specifiche per dimostrare la non convergenza.

3. Contributi Chiave e Risultati

A. Regolarità $r$-regolare e Struttura Automatica

Il risultato principale teorico è che, al contrario della sequenza di Golomb originale, ogni quasi-sequenza di Golomb di ordine $r$ è $r$-regolare (e quindi la sua sequenza delle differenze è $r$-automatica).

• Teorema 2.9: Dimostra che per ogni $r \ge 2$, la sequenza delle differenze $d(n)$ è $r$-automatica. Questo segna un passaggio fondamentale dal dominio delle leggi di potenza analitiche a quello delle sequenze automatiche.

B. Formule Esplicite e Denesting

Per $r \in \{2, 3, 4, 5\}$, l'autore fornisce formule di "denesting" che decompongono la sequenza in base alla rappresentazione in base $r$:

• Caso $r=2$: Viene trovata una formula ricorsiva nidificata di tipo Mallows:
  $$a(n+1) = 1 + a(n + 1 - a(a(n)+1) + a(a(n)-1))$$
  Inoltre, la sequenza soddisfa relazioni lineari semplici: $a(2n) = a(n) + a(n+1) - 1$.
• Caso $r=3$: La struttura richiede una sequenza di correzione binaria $\varepsilon(n)$ (automatica in base 3) per gestire le eccezioni. Le formule sono del tipo $a(3n) = \sum a(\dots) + 1 + \varepsilon(n-1)$.
• Casi $r=4, 5$: Vengono identificate quattro (per $r=4$) o due (per $r=5$) sequenze di correzione binarie che governano le deviazioni dalle formule lineari pure. Queste sono certificate da Walnut.

C. Non Convergenza del Rapporto $a(n)/n$

Un risultato sorprendente è che, mentre la sequenza di Golomb cresce come $n^{\phi-1}$, le quasi-sequenze crescono linearmente ($a(n) \asymp n$), ma il rapporto $a(n)/n$ non converge.

• Il rapporto oscilla tra due (o più) punti limite razionali distinti.
• Esempi:
  • Per $r=2$: i limiti sono $3/4$ e $2/3$.
  • Per $r=3$: i limiti sono $8/15$ e $5/8$.
  • Per $r=4$ e $r=5$: vengono identificati limiti razionali specifici (es. $25/48$ e $10/21$ per $r=4$).
• Questo comportamento è dovuto a un meccanismo di "feedback ritardato" nella struttura delle corse, descritto combinatoriamente come un automa cellulare booleano ($r=2$) o una sostituzione palindroma ($r=3$).

D. La Struttura Meta-Golomb (Congettura)

L'autore scopre una relazione numerica profonda tra le quasi-sequenze e la sequenza di Golomb originale.

• Sia $M(r)$ la massima molteplicità (numero di volte che un intero appare) nella quasi-sequenza di ordine $r$.
• Sia $j_k$ il più piccolo ordine $r$ tale che $M(r) \ge k$.
• Congettura 9.1: Le differenze tra questi indici di soglia sono governate dalla sequenza di Golomb stessa:
  $$j_{k+1} - j_k = G(k)$$
  Questo suggerisce che la sequenza di Golomb, pur essendo il limite "globale" ($r \to \infty$), riemerge come la legge che governa la struttura delle molteplicità all'interno della famiglia delle sequenze a memoria finita.

4. Significato e Implicazioni

• Transizione di Fase: Il lavoro illustra una transizione di fase matematica: passando da una memoria infinita (Golomb) a una memoria finita (quasi-Golomb), la natura della sequenza cambia radicalmente da sub-lineare e non-regolare a lineare e $r$-regolare.
• Struttura Combinatoria: Fornisce nuovi esempi ricchi di sequenze automatiche e regolari, collegando le ricorrenze nidificate (meta-Fibonacci) alla teoria degli automi cellulari e alle sostituzioni.
• Metodologia Ibrida: Dimostra l'efficacia dell'approccio ibrido che combina la deduzione matematica manuale per identificare i pattern con la verifica formale automatica (tramite Walnut) per le prove complete, specialmente per casi ad alta complessità ($r \ge 4$).
• Domande Aperte: Il paper solleva questioni aperte sulla natura del limite per $r \to \infty$, sulla convergenza delle medie di Cesàro per $r \ge 3$, e sull'estensione di queste strutture a finestre con "gap" diversi (gap-s).

In sintesi, il paper ridefinisce la comprensione delle sequenze autoreferenziali mostrando come una semplice restrizione della finestra di memoria trasformi una sequenza analitica complessa in una struttura combinatoria ricca, automatica e governata da leggi di regolarità precise, con un ritorno inaspettato della sequenza di Golomb come "meta-legge" della famiglia.