Brik's sequence: a strange recursion

Sintesi Tecnica: La Sequenza di Brik: Una Strana Ricorsione

Enunciato del Problema
Questo articolo indaga le proprietà di una sequenza di parole binarie $(B_i)_{i \ge 1}$ e della conseguente sequenza binaria infinita $b$, generate da una specifica iterazione ricorsiva proposta da Garo Brik nel 2018. La sequenza è definita dal caso base $B_1 = 101$ e dalla relazione di ricorrenza $B_{i+1} = B_i C_i$ per $i \ge 1$, dove $C_i$ è il suffisso di $B_i$ ottenuto rimuovendo i suoi primi $i$ simboli. Poiché $B_{i-1}$ è un prefisso di $B_i$ per ogni $i \ge 2$, queste parole convergono verso una singola sequenza infinita $b$. L'articolo mira a caratterizzare le proprietà combinatorie e aritmetiche di $b$, inclusa la sua ricorrenza, la complessità dei fattori, la natura morfica e la densità del simbolo '1'.

Metodologia
L'analisi impiega una combinazione di dimostrazioni per induzione, argomenti combinatori sui fattori delle parole e tecniche di teoria analitica dei numeri.

• Analisi Strutturale: Gli autori stabiliscono la lunghezza delle parole $B_i$ e le loro proprietà di suffisso mediante induzione banale. Utilizzano il concetto di "bordi" (prefissi che sono anche suffissi) per dimostrare che specifici indici sono "buoni", nel senso che $B_i$ è un bordo di $B_{\ell_i}$.
• Ricorrenza e Complessità: L'articolo analizza l'occorrenza dei fattori all'interno di $b$ per determinare le proprietà di ricorrenza. Caratterizza l'insieme di tutti i fattori validi identificando le sottostringhe vietate.
• Analisi della Crescita: Le posizioni iniziali di specifici pattern (in particolare le sequenze consecutive di $1$) sono tracciate utilizzando una relazione di ricorrenza, con i tassi di crescita analizzati mediante la notazione della tetrazione di Knuth.
• Calcolo della Densità: La densità dei $1$ è derivata analizzando il numero di $1$ nei prefissi di lunghezza $\ell_n = |B_n|$. Gli autori derivano una formula limite che coinvolge lo sviluppo binario della sequenza stessa e utilizzano l'analisi del termine di errore ($E(N)$) per estendere il limite da prefissi specifici a prefissi arbitrari.
• Dimostrazione di Trascendenza: Per determinare la natura del limite di densità $\alpha$, l'articolo applica una versione semplificata del criterio "balbettante" di Adamczewski e Bugeaud, che mette in relazione la struttura di ripetizione di una sequenza con la trascendenza del numero formato dal suo sviluppo binario.

Contributi e Risultati Chiave

1. Proprietà di Ricorrenza:

   • La parola infinita $b$ è dimostrata essere ricorrente (ogni fattore finito appare infinite volte) ma non uniformemente ricorrente.
   • L'articolo dimostra che $b$ contiene sequenze consecutive di $1$ di lunghezza arbitraria ($1^n$ per ogni $n$), il che preclude la ricorrenza uniforme. La posizione iniziale $r_n$ della prima occorrenza di $1^n$ segue la ricorrenza $r_{n+1} = 2^{r_{n-2}} + r_n$ per $n \ge 2$, portando a una crescita estremamente rapida (tetrazione).

2. Complessità dei Fattori:

   • Viene fornita una caratterizzazione completa dei fattori di $b$: una parola binaria è un fattore di $b$ se e solo se non contiene due $0$ consecutivi.
   • Di conseguenza, il numero di fattori distinti di lunghezza $n$ è esattamente $F_{n+2}$ (il $(n+2)$-esimo numero di Fibonacci). Ciò stabilisce che $b$ ha complessità dei fattori esponenziale.

3. Natura Non Morfica:

   • Sulla base della complessità esponenziale dei fattori, l'articolo conclude che $b$ non è morfica. Ciò deriva dal risultato di Ehrenfeucht, Lee e Rozenberg, che afferma che le sequenze morfiche devono avere complessità dei fattori polinomiale (specificamente $O(n^2)$).

4. Densità dei 1:

   • L'articolo dimostra che la densità asintotica dei $1$ in $b$, indicata con $\alpha = \lim_{n \to \infty} \frac{a(n)}{n}$, esiste.
   • Il valore è dato dalla formula $\alpha = 2 - 2\sum_{i \ge 1} b_i 2^{-i}$, dove $b_i$ è l'$i$-esimo bit della sequenza.
   • Il valore numerico è approssimativamente $0.64505878493452$.

5. Trascendenza:

   • La densità $\alpha$ è dimostrata essere trascendente. La prova si basa sul dimostrare che il numero associato $\beta = \sum b_i 2^{-i}$ è trascendente utilizzando il criterio balbettante. Poiché $\beta$ non può essere razionale (il che implicherebbe una complessità dei fattori limitata) e la sequenza esibisce la struttura "balbettante" richiesta ($B_{n+1}$ contiene $B_n$ seguito da una ripetizione di un suffisso), $\beta$ (e quindi $\alpha$) deve essere trascendente.

Significato e Affermazioni
L'articolo presenta una sequenza che, sebbene definita da una semplice regola iterativa, esibisce proprietà sottili e complesse non immediatamente evidenti. Il significato principale risiede nella scoperta di una sequenza che è ricorrente ma non uniformemente ricorrente, possiede complessità dei fattori esponenziale e genera una densità trascendente di $1$. Gli autori notano che la sequenza appare nell'OEIS (come A334820, mancante del termine iniziale) e sottolineano l'interazione tra la definizione ricorsiva e le proprietà aritmetiche risultanti.

L'articolo riconosce esplicitamente che questi risultati sono stati ottenuti attraverso esperimenti con APL e la collaborazione con ChatGPT 5.5 nel maggio 2026, con tutte le affermazioni successivamente riscritte e verificate dall'autore. Il lavoro funge da caso di studio sulle proprietà delle parole binarie definite ricorsivamente e sull'applicazione dei criteri di trascendenza alle sequenze combinatorie.