Superlinear complexity of the $(3/2)^n$ steering word

Resumo Técnico: Complexidade Superlinear da Palavra de Direcionamento $(3/2)^n$

Enunciado do Problema
O artigo investiga a dinâmica simbólica gerada pela órbita do número 1 sob o mapa $x \mapsto \frac{3}{2}x$, focando especificamente na sequência de erros de arredondamento para o inteiro mais próximo. Embora a distribuição da sequência $\|(\frac{3}{2})^n\|$ (distância ao inteiro mais próximo) seja um problema em aberto de longa data na teoria dos números, este trabalho desloca o foco para a "palavra de direcionamento" (steering word) $T = (t_n)_{n \geq 0}$. Esta palavra registra os transladados inteiros selecionados em cada etapa da dinâmica autônoma, definida por $t_n = 2m_{n+1} - 3m_n$, onde $m_n = \text{round}((\frac{3}{2})^n)$. A questão central abordada é a complexidade de subpalavras $p_T(k)$, que conta o número de fatores distintos de comprimento $k$ em $T$. O objetivo do artigo é provar que esta complexidade é superlinear, ou seja, $\lim_{k \to \infty} p_T(k)/k = \infty$.

Metodologia
A estratégia de prova é estruturada em três estágios distintos, transferindo métodos do estudo da complexidade de números algébricos (especificamente o método de Adamczewski–Bugeaud) para este cenário dinâmico. O argumento baseia-se fortemente no Teorema do Subespaço e é notado por ser totalmente formalizado em Lean-4.

1. Estágio 0: Identidades Exatas e Limites Incondicionais (Seções 2)
   O autor deriva uma "identidade de repetição" exata. Se um fator de comprimento $k$ se repete nas posições $a$ e $c$ ($a < c$), isso força a relação $3^k(\varepsilon_c - \varepsilon_a) = 2^k(\varepsilon_{c+k} - \varepsilon_{a+k})$, onde $\varepsilon_n$ é o erro de arredondamento.

   • Esta identidade gera uma condição de divisibilidade: $2^k \mid (m_c - m_a)$.
   • Combinado com as propriedades de crescimento da órbita, isso estabelece que repetições longas não podem ocorrer arbitrariamente tarde na palavra.
   • Resultado Incondicional: O artigo prova que $T$ não é eventualmente periódica e estabelece um limite inferior linear incondicional $p_T(k) \geq \frac{41}{24}k - 3$, que é estritamente acima do piso de Morse–Hedlund ($k+1$) para palavras aperiódicas.

2. Estágio 1: Redução a um Núcleo Diofantino (Seção 3)
   O problema de provar a complexidade superlinear é reduzido a uma única afirmação diofantina, referida como o Núcleo (K).

   • Afirmação (K): Para todo racional $\theta \in (0, 1)$, o conjunto de pares $(a, c)$ com $2 \leq a < c$ satisfazendo $\|(\frac{3}{2})^c - (\frac{3}{2})^a\| \leq \theta^c$ é finito.
   • Isso representa uma propriedade de "repulsão exponencial de pares", melhorando o limite inferior trivial da distância entre pontos da órbita de base $2^{-1}$ para uma base arbitrária $\theta < 1$.
   • A redução mostra que, se (K) for verdadeiro, então $p_T(k)/k \to \infty$.

3. Estágio 2: Estabelecendo o Núcleo (Seções 4 & 5)
   A prova de (K) é alcançada através da partição do conjunto de potenciais soluções em três "fatias" e aplicando resultados profundos de aproximação diofantina:

   • Fatia de Gap Limitado: Para gaps fixos $c-a$, a finitude é provada usando o Teorema Principal de Corvaja–Zannier (uma consequência do Teorema do Subespaço de Schmidt).
   • Fatia de Gap Enorme: Para a região onde $a \leq \epsilon' c$, a finitude também é estabelecida via o teorema de Corvaja–Zannier, tratando o problema como um caso específico de exclusão de pseudo-Pisot.
   • Faixa Intermediária: Para a região restante onde os gaps crescem, mas $a$ não é desprezível em relação a $c$, o autor emprega uma dicotomia de gap. Se o conjunto de soluções fosse infinito, seria possível extrair uma subfamília com gaps distintos. Isso leva a uma contradição via o teorema de tuplas S-unit de Nair–Kumar–Rout, o que implicaria que $(\frac{3}{2})^c$ é um inteiro para algum $c$, o que é impossível.

Contribuições Principais e Resultados

• Teorema Principal (Teorema 1.1): A complexidade de subpalavras da palavra de direcionamento $T$ é superlinear ($p_T(k)/k \to \infty$).
• Limite Inferior Incondicional: O artigo fornece um limite inferior linear incondicional explícito $p_T(k) \geq \frac{41}{24}k - 3$, derivado sem depender de conjecturas não provadas.
• Formalização: Todo o argumento é formalizado em Lean-4. A formalização depende apenas do Teorema do Subespaço de Evertse–Schlickewei em 3 variáveis, confirmando que as dependências dos resultados de Corvaja–Zannier e Nair–Kumar–Rout são consequências logicamente válidas do Teorema do Subespaço.
• Aperiodicidade: Uma prova rigorosa de que a palavra de direcionamento não é eventualmente periódica.

Significado e Alegações
O artigo afirma resolver a questão da complexidade para este sistema dinâmico autônomo específico, unindo dinâmica simbólica e aproximação diofantina.

• Transferência Metodológica: Ele adapta com sucesso o método de Adamczewski–Buleaud, tipicamente usado para números algébricos, para uma palavra dinâmica. O autor observa que a natureza autônoma da dinâmica de $(3/2)$ simplifica o controle de dados, permitindo que fatores repetidos se comprimam em desigualdades diofantinas limpas sem necessidade de ancoragem de prefixo.
• Dependência de Teoremas Profundos: A prova da superlinearidade é condicional ao teorema de Corvaja–Zannier (revisado por pares) e ao teorema de Nair–Kumar–Rout (um preprint na época da escrita). No entanto, a formalização em Lean-4 serve como uma verificação de que essas dependências são consequências logicamente sólidas do Teorema do Subespaço.
• Limitações: Os resultados relativos ao crescimento superlinear são inefetivos; o Teorema do Subespaço não fornece limites explícitos sobre o tamanho dos conjuntos excepcionais (o número de soluções para as desigualdades diofantinas). O artigo não pretende resolver o problema em aberto mais amplo sobre a densidade de $\|(\frac{3}{2})^n\| \to 0$, mas sim caracterizar a complexidade combinatória da sequência de arredondamento.