🔢 mathematics

Additive Bases from Primitive Dyck Words: Regular Underapproximations, Motzkin Coding, and Digit Lifting

Este artigo estabelece que todo número inteiro par positivo pode ser representado como uma soma de no máximo seis palavras de Dyck primitivas, com exceção de um conjunto finito de inteiros (incluindo 46, que requer oito) e o limiar eventual agudo de 848, ao alavancar uma conexão inédita entre caminhos de Dyck e codificação de Motzkin para provar teoremas de levantamento de dígitos e limites de geração.

Autores originais: Takayuki Kuriyama

Publicado 2026-07-28

📖 8 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Takayuki Kuriyama

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você é um detetive tentando resolver um tipo muito específico de enigma numérico. No mundo da matemática, existe um ramo chamado teoria aditiva dos números, que faz uma pergunta simples, mas difícil: você consegue construir todos os números em um determinado grupo somando alguns números "blocos de construção" especiais? Pense nisso como um jogo onde você tem um conjunto limitado de peças de Lego e quer saber se consegue construir todas as torres possíveis usando apenas essas peças. Às vezes, você pode precisar de apenas duas peças; outras vezes, precisará de dez. A "ordem" do jogo é o número máximo de peças que você precisará para construir qualquer torre.

Para jogar este jogo, os matemáticos usam um conjunto muito específico de blocos de construção. Esses blocos são números que, quando escritos em binário (a linguagem de 0s e 1s dos computadores), parecem parênteses perfeitamente equilibrados. Na matemática, estes são chamados de palavras de Dyck. Por exemplo, 1100 é uma palavra de Dyck válida porque, se você tratar 1 como um passo para "cima" e 0 como um passo para "baixo", o caminho sobe duas vezes e desce duas vezes, nunca descendo abaixo da linha de partida. O foco dos autores é um subconjunto especial destes, chamados de blocos primitivos, que são as peças "atômicas" que não podem ser decompostas em pares menores equilibrados. A grande questão que eles abordam é: qual é o número máximo de blocos primitivos que você precisa somar para criar qualquer número par?

Este artigo é uma aula magistral sobre como resolver esse enigma misturando duas ferramentas matemáticas diferentes. Os autores descobriram que esses blocos binários têm uma relação secreta com um outro tipo de caminho chamado caminho de Motzkin, que permite traduzir o problema para uma linguagem diferente (base-4) onde se torna muito mais fácil de resolver. Eles provaram que, embora a maioria dos números pares possa ser construída com apenas alguns desses blocos, existe um pequeno e obstinado grupo de números que é muito mais difícil de construir. Especificamente, eles descobriram que o número 46 é o caso mais difícil, exigindo oito blocos, enquanto alguns outros precisam de sete. No entanto, eles também provaram que, uma vez que você ultrapassa o número 848, você nunca precisará de mais do que seis blocos para construir qualquer número par. É uma história de encontrar os "piores cenários" em um vasto universo de números e provar exatamente onde o caos termina e a ordem começa.

A História dos Equilibristas Binários

Vamos mergulhar na aventura. Os autores, liderados por Takayuki Kuriyama, estão investigando um conjunto de números que provêm de uma linguagem de cadeias binárias equilibradas. Imagine que você tem uma sequência de luzes, algumas vermelhas (1) e outras azuis (0). Uma "palavra de Dyck" é uma sequência onde você tem o mesmo número de luzes vermelhas e azuis, e se você contar da esquerda para a direita, nunca terá mais luzes azuis do que vermelhas em nenhum momento. É como uma dança onde você não pode sair do palco até ter correspondido cada passo para cima com um passo para baixo.

Os autores estão interessados nos dançarinos "primitivos". Estes são as sequências que só retornam à linha de partida (altura zero) no final. Se uma sequência retorna ao zero no meio do caminho, ela é apenas duas danças menores coladas, não uma dança primitiva. Eles tratam essas sequências como números (lendo-as como binário) e perguntam: quantos desses números primitivos precisamos somar para obter qualquer número par?

O Código Secreto: De Binário para Base-4
A jogada brilhante deste artigo é perceber que estas sequências binárias possuem uma estrutura oculta. Se você agrupar os bits (00, 01, 10, 11), eles atuam como dígitos em um sistema de base-4 (0, 1, 2, 3). Os autores encontraram um mapeamento perfeito: cada número de Dyck primitivo (exceto pelo menor, que é 2) corresponde a um número de base-4 que começa com 3, termina com 0 e possui uma palavra "Motzkin" no meio.

Pense em uma palavra de Motzkin como um caminho que pode subir, descer ou permanecer plano, mas que nunca desce abaixo do chão. Esta conexão é a "Pedra de Roseta" do artigo. Ela permite que os autores traduzam um problema difícil sobre complexas sequências binárias em um problema mais limpo sobre números de base-4 e esses caminhos de caminhada plana. Esta tradução revela que o conjunto de números que eles estão estudando é "digitalmente fechado", o que significa que, se você tem um número no conjunto, pode frequentemente gerar novos números adicionando dígitos específicos.

A Estratégia de Duas Vias
Para resolver o enigma, os autores utilizam um ataque astuto de duas frentes, tratando os números pares com base em como eles se comportam quando divididos por 4.

A Via "Fácil" (Múltiplos de 4): Para números que são perfeitamente divisíveis por 4, os autores utilizam uma "subaproximação regular". Esta é uma forma sofisticada de dizer que eles encontraram um subconjunto mais simples e previsível dos números, que é fácil de trabalhar. Eles provaram que este conjunto mais simples é poderoso o suficiente para construir todos os grandes múltiplos de 4 usando apenas seis blocos.
A Via "Complicada" (Números 2 mod 4): Para números que deixam um resto de 2 quando divididos por 4 (como 6, 10, 14), o conjunto mais simples não é suficiente. Aqui, eles utilizam todo o poder da família "codificada por Motzkin". Eles provaram que esta família maior e mais complexa pode construir esses números usando apenas cinco blocos.

A Magia do "Levantamento" (Lifting)
Como eles sabem que isso funciona para todos os números grandes, não apenas para os que verificaram? Eles utilizam uma técnica de levantamento de dígitos (digit lifting). Imagine que você tem uma pequena escada que pode alcançar certa altura. Os autores provaram um teorema que diz: se você consegue construir um intervalo contínuo de números com um certo número de blocos, você pode "elevar" essa habilidade de construir todos os números maiores simplesmente adicionando dígitos específicos às extremidades dos blocos. É como ter uma regra mágica que diz: "Se você consegue construir uma torre de altura 100, você pode automaticamente construir torres de altura 400, 401, 402 e assim por diante". Isso permite que eles peguem uma lista finita de números verificados e provem que o padrão se mantém para sempre.

Os Resultados: Os Números Obstinados
Após estabelecerem suas ferramentas, os autores foram ao trabalho classificando as exceções. Eles descobriram que, embora a maioria dos números pares seja fácil de construir, existe uma lista específica de números "obstinados" que requerem mais de seis blocos.

O Campeão da Dificuldade: O número 46 é o mais difícil de todos. Ele não pode ser construído com sete ou menos blocos; ele exige estritamente oito.
Os Vice-Campeões: Existem outros dez números que precisam de sete blocos: 34, 44, 98, 154, 198, 202, 206, 838, 842 e 846.
O Limiar: Os autores provaram que 848 é o número mágico. Todo número par de 848 em diante pode ser construído com seis ou menos blocos.

Eles não apenas adivinharam esses números; eles usaram cálculos computacionais exatos para verificar cada caso até o limiar e usaram suas provas matemáticas para mostrar que isso se mantém para o infinito.

Por Que Isso Importa
Este artigo é um belo exemplo de como diferentes áreas da matemática — ciência da computação (linguagens e autômatos), combinatória (caminhos e árvores) e teoria dos números (adição) — podem dançar juntas. Os autores não apenas encontraram uma lista de números; eles construíram uma estrutura. Eles mostraram que, mesmo para um conjunto de números definido por um padrão complexo e não repetitivo (uma linguagem "livre de contexto"), você pode encontrar um padrão simples e repetitivo (uma linguagem "regular") que cobre a maior parte do terreno e, então, usar a complexidade total para preencher as lacunas.

Eles também descobriram que a "ordem" do jogo muda dependendo das regras. Se você olhar apenas para os múltiplos de 4, você sempre precisará de apenas 5 blocos. Mas se você incluir os números que são 2 mod 4, o requisito salta para 6. E se você considerar o pior cenário absoluto (incluindo o número 46), você precisará de 8.

No fim, o artigo nos dá um mapa completo. Sabemos exatamente quais números são os problemáticos, sabemos o limite exato onde o problema termina e temos um algoritmo construtivo (uma receita passo a passo) para construir qualquer grande número par usando esses blocos binários especiais. Ele transforma um problema de aparência caótica em um sistema perfeitamente ordenado, provando que, mesmo no mundo dos números abstratos, sempre há um padrão esperando para ser encontrado.

Resumo Técnico: Bases Aditivas de Palavras de Dyck Primitivas

Enunciado do Problema
Este artigo investiga representações aditivas de inteiros pares positivos utilizando somandos extraídos do conjunto $N_pD$ . Este conjunto consiste em zero e nos valores inteiros de palavras de Dyck primitivas interpretadas como números binários. Uma palavra de Dyck é uma sequência balanceada de 1s (passos para cima) e 0s (passos para baixo); uma palavra é primitiva se o seu caminho associado retorna à altura zero apenas ao final. A questão central é determinar a ordem aditiva deste conjunto: especificamente, o menor inteiro $h$ tal que todo inteiro par suficientemente grande pode ser expresso como uma soma de no máximo $h$ elementos de $N_pD$ , e classificar o conjunto exato de inteiros "excepcionais" que requerem mais do que um determinado número de somandos.

Metodologia
Os autores empregam uma abordagem híbrida combinando teoria de linguagens formais, teoria combinatória dos números e algoritmos construtivos:

Codificação de Blocos Posicionais: A percepção estrutural central é uma bijeção entre palavras de Dyck primitivas e palavras de Motzkin de duas cores via uma codificação de blocos em base 4. Ao parear dígitos binários consecutivos, os autores mapeiam palavras de Dyck primitivas (excluindo a palavra "10") para palavras em base 4 da forma $3w0$ , onde $w$ é uma palavra de Motzkin de duas cores. Isso permite que os autores traduzam a linguagem de Dyck não regular para uma estrutura compatível com a aritmética posicional em base 4.
Subaproximação Regular: Para lidar com inteiros congruentes a $0 \pmod 4$ , os autores constroem uma subaproximação regular explícita da linguagem de Dyck primitiva. Este subconjunto, definido pela expressão regular $11(01|10)^*00$ , corresponde a palavras de Motzkin compostas exclusivamente pelos dígitos $\{1, 2\}$ . Este subconjunto regular é passível de métodos de autômatos finitos e fornece uma cobertura para múltiplos de 4.
Elevação e Propagação de Dígitos (Digit Lifting): O artigo introduz um Teorema de Elevação de Dígitos de Intervalo. Este teorema prova que, se um conjunto $A$ satisfaz uma propriedade de fechamento (especificamente $4A + \{1, 2\} \subseteq A$ ), um intervalo finito de números representáveis pode ser recursivamente estendido para uma cauda infinita. Isso permite que os autores convertam certificados computacionais finitos (conjuntos-soma de números pequenos) em provas de representabilidade para todos os inteiros suficientemente grandes.
Certificados Finitos e Busca Exaustiva: A prova baseia-se em aritmética de inteiros exata para computar conjuntos-soma de pequenos geradores. Os autores verificam intervalos específicos onde os conjuntos-soma da família regular (para múltiplos de 4) e da família codificada por Motzkin (para inteiros $\equiv 2 \pmod 4$ ) se sobrepõem suficientemente para disparar a propagação da elevação de dígitos.

Principais Contribuições

Caracterização Exata em Base 4: O artigo estabelece a identidade $DP = \{10\} \cup \phi(3 \cdot \text{Motz} \cdot 0)$ , onde $\phi$ é um morfismo uniforme que mapeia dígitos de base 4 em pares binários. Isso fornece um elo estrutural preciso entre palavras de Dyck primitivas e caminhos de Motzkin que preserva os valores posicionais canônicos.
Classificação de Inteiros Excepcionais: Os autores classificam completamente os inteiros pares positivos que requerem mais de seis somandos.
- O inteiro 46 é o único inteiro par que requer oito somandos.
- Os inteiros 34, 44, 98, 154, 198, 202, 206, 838, 842 e 846 requerem exatamente sete somandos.
- Todo outro inteiro par positivo requer no máximo seis.
Limiares Estritos (Sharp Thresholds): O artigo identifica 848 como o limiar assintótico estrito: todo inteiro par $N \ge 848$ é uma soma de no máximo seis números de Dyck primitivos.
Análise da Ordem Assintótica: Os autores distinguem entre a "ordem relativa" (para todos os inteiros pares) e a "ordem assintótica" (para inteiros pares suficientemente grandes).
- O conjunto $N_pD$ é uma base aditiva relativa de ordem 8 para os inteiros pares (devido à exceção em 46).
- A ordem assintótica relativa é 6.
- A família "dividida pela metade" $P$ (onde $N_pD = \{0, 2\} \cup 4P$ ) tem uma ordem aditiva assintótica de 5.
Algoritmos Construtivos: O mecanismo de elevação de dígitos gera um algoritmo construtivo que produz representações para grandes inteiros em $O(\log n)$ estágios recursivos, convertendo representações de sementes finitas em caudas infinitas.

Resultos e Significância
O artigo demonstra que, embora a linguagem das palavras de Dyck primitivas seja determinística livre de contexto (e, portanto, não regular), suas propriedades aditivas podem ser efetivamente analisadas separando o problema em classes de resíduos módulo 4.

Para $N \equiv 0 \pmod 4$ , uma subaproximação regular é suficiente para provar que seis somandos são eventualmente suficientes.
Para $N \equiv 2 \pmod 4$ , a prova requer o poder total da família codificada por Motzkin e uma cobertura de cinco somandos, o que, combinado com a necessidade de usar um número ímpar do somando '2', eleva o limite assintótico para seis.

A significância do trabalho reside na aplicação bem-sucedida de subaproximações regulares a uma linguagem não regular para resolver um problema de teoria aditiva dos números. Fornece um exemplo concreto onde a interação entre a estrutura da linguagem formal (Dyck vs. Motzkin) e sistemas de numeração posicional produz limites computáveis e precisos. Os autores explicitamente observam que o limite de seis é assintoticamente ótimo, pois a sequência $N_k = 10 \cdot 4^{k+1} - 6$ requer exatamente seis somandos para cada $k \ge 2$ .

Todos os certificados finitos e a classificação dos valores excepcionais são verificados por programas suplementares usando aritmética de inteiros exata, garantindo a reprodutibilidade dos resultados. O artigo conclui que 848 é o menor inteiro par tal que todos os inteiros pares maiores são representáveis por no máximo seis números de Dyck primitivos, enquanto 46 permanece como a única exceção que requer oito.

A História dos Equilibristas Binários

Mais como este