Almost Golomb Sequences

Resumo Técnico: Sequências Quase de Golomb

1. O Problema e o Contexto

O artigo investiga uma generalização da Sequência de Golomb clássica (OEIS A001462). A sequência de Golomb, $G(n)$, é definida como a única sequência não decrescente de inteiros positivos onde o inteiro $n$ aparece exatamente $G(n)$ vezes. Ela satisfaz a regra autorreferencial global:
$$G\left(\sum_{k=1}^n G(k)\right) = n$$
Esta sequência cresce suavemente como uma potência de $n$ (governada pela razão áurea $\phi$) e não é $k$-regular para nenhum $k \ge 2$.

O problema central abordado é: O que acontece se substituirmos a soma cumulativa infinita (memória total) por uma janela deslizante de tamanho fixo $r$?
Os autores definem as Sequências Quase de Golomb de ordem $r$, denotadas por $a_r(n)$, como a sequência não decrescente de inteiros positivos que satisfaz:
$$a_r\left(a_r(n) + a_r(n-1) + \dots + a_r(n-r+1)\right) = n$$
com $a_r(k) = 0$ para $k \le 0$, e escolhendo o menor inteiro possível que satisfaça a condição (regra gulosa).

2. Metodologia

A abordagem combina análise combinatória, teoria dos números e teoria da computação (sequências automáticas e regulares).

• Estrutura de Corridas (Runs): O artigo primeiro estabelece a estrutura global das sequências, provando que os valores aumentam em passos de 0 ou 1 e que as posições de início de cada novo valor são estritamente crescentes.
• Regularidade e Automaticidade: Utiliza-se o critério de Allouche-Shallit para provar que as sequências são $r$-regulares. A prova envolve reduzir a diferença $d(n) = a(n+1) - a(n)$ a uma janela finita de dados locais.
• Fórmulas de "Desemaranhamento" (Denesting): Para valores pequenos de $r$ ($2, 3, 4, 5$), os autores derivam fórmulas recursivas explícitas baseadas na representação $r$-ádica de $n$ (ex: $a(rn+i) = \dots$).
• Certificação Computacional: Para $r=4$ e $r=5$, as identidades recursivas complexas são identificadas matematicamente e depois certificadas formalmente usando o provador de teoremas Walnut, que verifica a automaticidade e as recorrências booleanas das sequências de correção.
• Análise Assintótica: O comportamento de $a(n)/n$ é estudado ao longo de progressões geométricas para determinar a convergência ou oscilação.

3. Principais Contribuições e Resultados

A. Mudança de Natureza: De Analítico para Automático
A truncagem da memória altera fundamentalmente a natureza da sequência:

• Golomb ($r \to \infty$): Crescimento suave, sublinear ($n^{\phi-1}$), não regular.
• Quase Golomb ($r$ finito): Crescimento linear ($a(n) \asymp n$) com oscilações discretas. A sequência torna-se $r$-regular para todo $r \ge 2$.

B. Fórmulas Explícitas e Estrutura $r$-ádica
O artigo fornece fórmulas de "desemaranhamento" para $r \in \{2, 3, 4, 5\}$:

• $r=2$: A sequência satisfaz uma recorrência análoga à de Mallows: $a(n+1) = 1 + a(n + 1 - a(a(n)+1) + a(a(n)-1))$. A sequência de diferenças é gerada por um autômato celular booleano simples.
• $r=3$: A estrutura é descrita por uma regra de substituição palindrômica.
• $r=4, 5$: As fórmulas envolvem sequências de correção binárias ($\epsilon_i$) que são $r$-automáticas.

C. Não-Convergência da Razão $a(n)/n$
Um resultado crucial é que, ao contrário da sequência de Golomb, a razão $a(n)/n$ não converge para qualquer $r \ge 2$.

• A razão oscila entre dois (ou mais) pontos limites racionais distintos.
• Exemplos:
  • $r=2$: Oscila entre $3/4$ e $2/3$.
  • $r=3$: Oscila entre $8/15$ e $5/8$.
  • $r=4$ e $r=5$: Oscilações similares com limites racionais específicos.
• As médias de Cesàro também não convergem para $r=2$.

D. Interpretações Combinatórias

• Para $r=2$, a multiplicidade de um valor $m$ na sequência depende do segundo bit mais significativo de $m-1$ em binário.
• Para $r=3$, a estrutura das diferenças é descrita por blocos palindrômicos.

E. A "Meta-Estrutura" de Golomb (Conjectura)
O resultado mais surpreendente é a descoberta de que a própria Sequência de Golomb governa a estrutura das sequências quase de Golomb.

• Seja $M(r)$ a multiplicidade máxima de qualquer valor na sequência de ordem $r$.
• Seja $j_k$ o menor $r$ tal que $M(r) \ge k$.
• Os dados numéricos sugerem que as diferenças entre esses limiares seguem exatamente a sequência de Golomb:
  $$j_{k+1} - j_k = G(k) \quad \text{para } k \ge 4$$
  onde $G(k)$ é o $k$-ésimo termo da sequência de Golomb original.
• Isso implica que a sequência truncada (que define a família) reaparece como a lei que controla a multiplicidade máxima dentro dessa mesma família. O artigo reduz essa conjectura a duas hipóteses precisas: a "Conjectura do Prefixo" e o "Lema de Dominação".

4. Significado e Impacto

• Transição de Regimes: O trabalho demonstra claramente como a introdução de uma janela de memória finita transforma um problema analítico (crescimento suave, transcendental) em um problema combinatório/automático (crescimento linear, regularidade).
• Novas Classes de Sequências: Estabelece uma nova família de sequências autorreferenciais que são $r$-regulares, conectando a teoria das sequências de Golomb com a teoria das sequências automáticas e regulares.
• Fenômeno de Auto-Referência Meta: A descoberta de que a sequência original de Golomb emerge como o "controle de multiplicidade" das suas próprias variantes truncadas sugere uma profundidade estrutural não prevista anteriormente, onde a solução global governa as propriedades locais das soluções aproximadas.
• Ferramentas Computacionais: O uso do provador Walnut para certificar identidades complexas em $r=4$ e $r=5$ serve como um modelo para a prova de propriedades em sequências definidas por regras recursivas complexas.

Em suma, o artigo redefine o entendimento das sequências autorreferenciais, mostrando que a restrição de memória não apenas altera o crescimento, mas revela uma estrutura hierárquica onde a sequência original de Golomb atua como um "esqueleto" para suas variantes finitas.