On a sequence of Kimberling and its relationship to the Tribonacci word

Este artigo prova as conjecturas de Clark Kimberling sobre a sequência binária que ele definiu, estabelecendo sua relação com a palavra de Tribonacci e determinando sua complexidade de subpalavras e expoente crítico, utilizando o provador de teoremas Walnut.

O essencial

Imagine que você tem um jogo de "crescimento de plantas" muito especial, onde cada folha e cada galho segue regras estranhas para se multiplicar. É assim que funciona o sequência B, um padrão infinito de zeros e uns (0 e 1) criado pelo matemático Clark Kimberling em 2017.

Este artigo é como um manual de instruções escrito por três detetives matemáticos (Lubomíra, Edita e Jeffrey) que decidiram desvendar os mistérios dessa planta. Eles usaram uma mistura de lógica clássica e um "robô matemático" chamado Walnut para provar que as previsões de Kimberling estavam corretas e descobriram segredos escondidos sobre como essa sequência se conecta com o mundo.

Aqui está a explicação do que eles fizeram, usando analogias simples:

1. A Planta que se Multiplica (A Regra de Crescimento)

Kimberling criou uma regra de crescimento um pouco confusa. Imagine que você tem um jardim com blocos de plantas:

• Se você vê um bloco "00" (duas folhas juntas), ele vira "0101".
• Se você vê um "1", ele vira "10".
• Se você vê um "0" sozinho, ele vira "0".

Você começa com duas folhas: 00.
Na próxima etapa, vira 0101. Depois 010010, e assim por diante.
O mistério era: Quanto essa planta cresce a cada passo? Kimberling chutou um número, mas não tinha certeza. Os autores usaram o robô Walnut (que é como um super-cálculo que verifica lógica automaticamente) para provar que o tamanho da planta segue exatamente a fórmula que ele chutou. É como ter uma régula mágica que confirma que a planta cresce exatamente 2, 4, 6, 10... unidades a cada dia.

2. O Espelho do Mundo Tribonacci (A Conexão Secreta)

A parte mais mágica do artigo é descobrir que essa planta estranha (a sequência B) não é uma ilha. Ela é, na verdade, uma versão disfarçada de uma planta muito famosa chamada Palavra Tribonacci.

• A Palavra Tribonacci é como um "avô" de padrões matemáticos, conhecido por ser extremamente equilibrado e bonito.
• Os autores descobriram que, se você pegar a Palavra Tribonacci e aplicar um "filtro de tradução" (uma regra simples que troca os números), você obtém exatamente a sequência de Kimberling.

É como se a sequência B fosse um filme dublado de um clássico. O roteiro é o mesmo (a estrutura Tribonacci), mas os atores falam uma língua ligeiramente diferente. Isso é importante porque, ao entender o "avô" (Tribonacci), eles puderam entender o "neto" (Kimberling) sem precisar reinventar a roda.

3. O Robô de Previsão (O Autômato)

Para estudar essa sequência em detalhes, os autores construíram um robô de papel (um autômato finito).
Imagine que você quer saber qual é a 1.000.000ª folha dessa planta. Em vez de crescer a planta até lá (o que levaria anos), você dá o número 1.000.000 para o robô. O robô olha para o número escrito em um código especial (chamado "representação Tribonacci") e, em um piscar de olhos, diz: "A folha é um 0" ou "A folha é um 1".
Esse robô permite que eles provem matematicamente coisas que seriam impossíveis de verificar à mão.

4. O Que Eles Descobriram? (As Propriedades)

Com o robô e a conexão com o "avô" Tribonacci, eles descobriram duas coisas principais:

• A Complexidade (Quantos Padrões Existem?):
  Eles contaram quantos "blocos" diferentes de tamanho $n$ aparecem na sequência. Descobriram que a sequência é tão rica em padrões que, para cada tamanho, existem exatamente o dobro de possibilidades do que o tamanho em si (uma fórmula chamada $2n$). Isso a coloca em uma categoria especial de sequências matemáticas chamadas "Palavras de Rote". É como dizer que, não importa o tamanho do mosaico que você olhar, sempre há uma quantidade perfeita e previsível de peças diferentes.

• O Exponente Crítico (O Recorde de Repetição):
  Eles perguntaram: "Qual é o maior pedaço repetido que essa sequência pode ter?"
  Imagine uma música que repete um refrão. O "exponente crítico" é a medida de quão longo esse refrão pode ser antes de a música ficar chata ou quebrar. Eles provaram que o recorde de repetição dessa sequência é um número específico (aproximadamente 3,19). Isso significa que você nunca verá um padrão repetido mais de 3,19 vezes seguidas. É um limite rígido imposto pela natureza matemática da planta.

Resumo Final

Em suma, este artigo é uma jornada de detetive:

1. O Caso: Uma sequência de zeros e uns criada por um matemático amador com regras estranhas.
2. A Investigação: Usando um robô matemático (Walnut) e comparando com um "clássico" famoso (Tribonacci).
3. A Solução: Eles provaram que as regras de crescimento funcionam, descobriram que a sequência é uma versão disfarçada de um padrão famoso, e mediram exatamente quão complexa e repetitiva ela é.

É um exemplo lindo de como a matemática moderna usa computadores não apenas para calcular, mas para provar verdades sobre padrões infinitos que o olho humano jamais conseguiria ver sozinho.

Resumo técnico

Aqui está um resumo técnico detalhado do artigo "On a sequence of Kimberling and its relationship to the Tribonacci word", apresentado em português.

Título: Sobre uma sequência de Kimberling e sua relação com a palavra Tribonacci

Autores: Lubomíra Dvořáková, Edita Pelantová e Jeffrey Shallit.

---

1. O Problema

O artigo foca na análise da sequência binária $B$ (OEIS A288462), definida por Clark Kimberling em 2017. A sequência é gerada como o ponto fixo infinito de regras de inflação (substituição) mais complexas do que morfismos padrão:

• Regras de inflação: $00 \mapsto 0101$,$1 \mapsto 10$,$0 \mapsto 0$.
• A construção inicia com $B_0 = 00$. Para obter $B_{i+1}$, o bloco $B_i$ é fatorado em blocos máximos do tipo $00$,$0$e$1$, e as regras são aplicadas a esses blocos.

Kimberling fez várias conjecturas sobre esta sequência, incluindo:

1. A fórmula para o comprimento dos iterados $|B_i|$.
2. A relação entre os índices das ocorrências de 0 e 1 na sequência e constantes específicas (relacionadas ao número Tribonacci).
3. Propriedades de complexidade e expoente crítico da sequência.

O desafio reside no fato de que as regras de inflação envolvem uma substituição não puramente morfística (depende do contexto de blocos máximos), tornando a análise combinatória direta difícil.

2. Metodologia

Os autores utilizam uma abordagem híbrida combinando teoria dos autômatos, combinatória em palavras e prova automática de teoremas.

• Prova Automática (Walnut): Utilizam o provador de teoremas Walnut, que permite decidir propriedades de sequências automáticas expressas em lógica de primeira ordem. Eles construíram autômatos finitos determinísticos com saída (DFAO) que computam a sequência $B$ e suas propriedades (como contagem de fatores e posições de símbolos) usando a representação Tribonacci dos inteiros.
• Relação com a Palavra Tribonacci (TR): Estabelecem uma conexão teórica profunda entre $B$ e a palavra Tribonacci infinita ($TR$), que é o ponto fixo do morfismo $0 \to 01$,$1 \to 02$,$2 \to 0$.
• Análise de Fatores Bispeciais: Para determinar a complexidade de fatores e o expoente crítico, os autores analisam os "fatores bispeciais" (fatores que podem ser estendidos à esquerda e à direita de ambas as formas possíveis) e suas "palavras de retorno" (return words).

3. Principais Contribuições e Resultados

A. Conexão com a Palavra Tribonacci

O teorema central (Teorema 2) demonstra que a sequência de Kimberling $B$ é a imagem da palavra Tribonacci sob uma morfismo simples, precedida por um 0:
$$B = 0 \cdot f(TR)$$
Onde $f: 0 \mapsto 10, 1 \mapsto 0, 2 \mapsto 1$.
Isso permite tratar $B$ como uma sequência automática, facilitando a aplicação de ferramentas computacionais como o Walnut.

B. Confirmação das Conjecturas de Kimberling

• Comprimento dos Iterados: Provam que o comprimento $|B_i|$ segue a recorrência $c_i = 2c_{i-1} - c_{i-4}$ (para $i \ge 4$), confirmando a conjectura de Kimberling sobre o crescimento da sequência.
• Índices de Ocorrência: Estabelecem limites precisos para os índices das $n$-ésimas ocorrências de 0 ($I_0(n)$) e 1 ($I_1(n)$) na sequência:
  • $I_0(n) \approx \psi n$, onde $\psi \approx 1.83928$ é a constante Tribonacci.
  • $I_1(n) \approx \gamma n$, onde $\gamma = (\psi^2 + 1)/2 \approx 2.19148$.
    Os autores provam desigualdades rigorosas (ex: $\lfloor \psi n \rfloor - 2 \le I_0(n) \le \lfloor \psi n \rfloor + 2$), refinando as conjecturas originais.

C. Complexidade de Fatores

• Teorema 5: A complexidade de fatores de $B$ (número de blocos distintos de comprimento $n$) é dada por $p(n) = 2n$ para todo $n \ge 1$.
• Isso classifica $B$ como uma palavra de Rote, uma classe de sequências binárias com complexidade linear máxima, intimamente ligada às palavras de Sturm.

D. Expoente Crítico

• Teorema 6: Determinam o expoente crítico de $B$ (o supremo dos expoentes de todas as suas potências):
  $$ce(B) = 2 + \frac{1}{\psi - 1} \approx 3.19148788$$
• O valor é idêntico ao expoente crítico da palavra Tribonacci. A prova envolve a análise assintótica das razões entre o comprimento dos fatores bispeciais e suas palavras de retorno mais curtas.

E. Equilíbrio (Balance)

• Teorema 3: A sequência $B$ é 3-equilibrada, mas não 2-equilibrada. Isso significa que, para qualquer dois fatores de mesmo comprimento, a diferença no número de 1s é no máximo 3.

4. Significado e Impacto

• Validação de Conjecturas: O trabalho resolve definitivamente as conjecturas abertas por Clark Kimberling sobre esta sequência específica, demonstrando a utilidade de ferramentas computacionais modernas na teoria dos números e combinatória.
• Metodologia Híbrida: O artigo serve como um "primer" (introdução prática) sobre como atacar sequências complexas definidas por regras de inflação não padrão, combinando intuição matemática (relação com TR) com verificação rigorosa via autômatos e lógica.
• Classe de Sequências: Ao provar que $B$ é uma palavra de Rote e determinar seu expoente crítico, o trabalho enriquece o conhecimento sobre a estrutura de sequências automáticas e suas propriedades de repetição e complexidade.
• Reprodutibilidade: O uso do código Walnut (fornecido no anexo do artigo) permite que outros pesquisadores verifiquem e estendam os resultados, promovendo a ciência aberta e a prova formal em combinatória.

Em resumo, o artigo transforma uma curiosidade numérica definida por regras de inflação complexas em um objeto matemático bem compreendido, revelando sua profunda conexão com a palavra Tribonacci e estabelecendo suas propriedades fundamentais de forma rigorosa.