Brik's sequence: a strange recursion

Resumo Técnico: A Sequência de Brik: Uma Recursão Estranha

Enunciado do Problema
Este artigo investiga as propriedades de uma sequência de palavras binárias $(B_i)_{i \ge 1}$ e da sequência binária infinita resultante $b$, geradas por uma iteração recursiva específica proposta por Garo Brik em 2018. A sequência é definida pelo caso base $B_1 = 101$ e pela relação de recorrência $B_{i+1} = B_i C_i$ para $i \ge 1$, onde $C_i$ é o sufixo de $B_i$ obtido removendo seus primeiros $i$ símbolos. Como $B_{i-1}$ é um prefixo de $B_i$ para todo $i \ge 2$, essas palavras convergem para uma única sequência infinita $b$. O artigo busca caracterizar as propriedades combinatórias e aritméticas de $b$, incluindo sua recorrência, complexidade de fatores, natureza morfica e a densidade do símbolo '1'.

Metodologia
A análise emprega uma combinação de provas indutivas, argumentos combinatórios sobre fatores de palavras e técnicas de teoria analítica dos números.

• Análise Estrutural: Os autores estabelecem o comprimento das palavras $B_i$ e suas propriedades de sufixo via indução trivial. Eles utilizam o conceito de "bordas" (prefixos que também são sufixos) para provar que índices específicos são "bons", significando que $B_i$ é uma borda de $B_{\ell_i}$.
• Recorrência e Complexidade: O artigo analisa a ocorrência de fatores dentro de $b$ para determinar propriedades de recorrência. Caracteriza o conjunto de todos os fatores válidos identificando substrings proibidos.
• Análise de Crescimento: As posições iniciais de padrões específicos (especificamente sequências de $1$'s) são rastreadas usando uma relação de recorrência, com taxas de crescimento analisadas usando a notação de tetração de Knuth.
• Cálculo de Densidade: A densidade de $1$'s é derivada analisando o número de $1$'s em prefixos de comprimento $\ell_n = |B_n|$. Os autores derivam uma fórmula limite envolvendo a expansão binária da própria sequência e usam análise do termo de erro ($E(N)$) para estender o limite de prefixos específicos para prefixos arbitrários.
• Prova de Transcendência: Para determinar a natureza do limite de densidade $\alpha$, o artigo aplica uma versão simplificada do critério de "gagueira" de Adamczewski e Bugeaud, que relaciona a estrutura de repetição de uma sequência com a transcendência do número formado por sua expansão binária.

Principais Contribuições e Resultados

1. Propriedades de Recorrência:

   • A palavra infinita $b$ é provada ser recorrente (todo fator finito aparece infinitas vezes) mas não uniformemente recorrente.
   • O artigo demonstra que $b$ contém sequências arbitrariamente longas de $1$'s ($1^n$ para todo $n$), o que exclui a recorrência uniforme. A posição inicial $r_n$ da primeira ocorrência de $1^n$ segue a recorrência $r_{n+1} = 2^{r_{n-2}} + r_n$ para $n \ge 2$, levando a um crescimento extremamente rápido (tetração).

2. Complexidade de Fatores:

   • É fornecida uma caracterização completa dos fatores de $b$: uma palavra binária é um fator de $b$ se e somente se não contiver dois $0$'s consecutivos.
   • Consequentemente, o número de fatores distintos de comprimento $n$ é exatamente $F_{n+2}$ (o $(n+2)$-ésimo número de Fibonacci). Isso estabelece que $b$ tem complexidade de fatores exponencial.

3. Natureza Não-Mórfica:

   • Com base na complexidade de fatores exponencial, o artigo conclui que $b$ não é mórfica. Isso segue do resultado de Ehrenfeucht, Lee e Rozenberg, que afirma que sequências mórficas devem ter complexidade de fatores polinomial (especificamente $O(n^2)$).

4. Densidade de 1's:

   • O artigo prova que a densidade assintótica de $1$'s em $b$, denotada $\alpha = \lim_{n \to \infty} \frac{a(n)}{n}$, existe.
   • O valor é dado pela fórmula $\alpha = 2 - 2\sum_{i \ge 1} b_i 2^{-i}$, onde $b_i$ é o $i$-ésimo bit da sequência.
   • O valor numérico é aproximadamente $0,64505878493452$.

5. Transcendência:

   • A densidade $\alpha$ é provada ser transcendental. A prova baseia-se em mostrar que o número associado $\beta = \sum b_i 2^{-i}$ é transcendental usando o critério de "gagueira". Como $\beta$ não pode ser racional (o que implicaria complexidade de fatores limitada) e a sequência exibe a estrutura de "gagueira" requerida ($B_{n+1}$ contém $B_n$ seguido por uma repetição de um sufixo), $\beta$ (e portanto $\alpha$) deve ser transcendental.

Significado e Alegações
O artigo apresenta uma sequência que, embora definida por uma regra iterativa simples, exibe propriedades sutis e complexas não imediatamente aparentes. O significado principal reside na descoberta de uma sequência que é recorrente mas não uniformemente recorrente, possui complexidade de fatores exponencial e gera uma densidade transcendental de $1$'s. Os autores notam que a sequência aparece na OEIS (como A334820, faltando o termo inicial) e destacam a interação entre a definição recursiva e as propriedades aritméticas resultantes.

O artigo reconhece explicitamente que esses resultados foram obtidos através de experimentação com APL e colaboração com o ChatGPT 5.5 em maio de 2026, com todas as alegações subsequentemente reescritas e verificadas pelo autor. O trabalho serve como um estudo de caso nas propriedades de palavras binárias definidas recursivamente e na aplicação de critérios de transcendência a sequências combinatórias.