Dyck Words, Pattern Avoidance, and Automatic Sequences

Este artigo investiga as palavras de Dyck em sequências binárias, demonstrando que palavras livres de potências $7/3$ possuem nível de aninhamento limitado, caracterizando explicitamente os fatores da palavra de Thue-Morse que são Dyck e estabelecendo limites superiores e inferiores rigorosos para a contagem desses fatores.

O essencial

Imagine que você está construindo uma torre de blocos, mas com uma regra muito específica: cada bloco preto (que chamaremos de "0") é uma base que precisa ser coberta, e cada bloco branco (que chamaremos de "1") é uma tampa que fecha uma base.

Para que a sua torre seja "perfeita" (o que os matemáticos chamam de Palavra de Dyck), você precisa ter exatamente o mesmo número de bases e tampas, e, mais importante, você nunca pode colocar uma tampa se não houver uma base esperando por ela. É como tentar fechar parênteses: (()) está certo, mas )( ou (() estão errados.

Os autores deste artigo, Lucas Mol, Narad Rampersad e Jeffrey Shallit, são como detetives que estudam sequências infinitas de blocos pretos e brancos. Eles querem saber: quão complexas podem ser essas torres perfeitas que aparecem escondidas dentro dessas sequências?

Aqui está o resumo da investigação deles, traduzido para o dia a dia:

1. O Limite da Complexidade (A Regra do "7/3")

Imagine que você tem uma sequência de blocos onde você não pode repetir padrões demais. Por exemplo, se você tiver um padrão que se repete 2,33 vezes (o que os matemáticos chamam de potência 7/3), a sequência é considerada "livre de repetições excessivas".

• A Descoberta: Os autores provaram que, se você tentar construir uma torre perfeita (Dyck) dentro de uma sequência que não repete padrões demais (livre de potência 7/3), a sua torre não pode ser muito alta.
• A Analogia: É como se houvesse um "teto de vidro" invisível. Você pode construir torres de 3 andares, mas se tentar fazer a 4ª, a estrutura desmorona porque a sequência original não permite a repetição necessária para sustentar essa altura.
• A Surpresa: Se você relaxar a regra e permitir repetições um pouco maiores, você pode construir torres infinitamente altas! A barreira de 7/3 é o ponto exato onde a mágica acontece.

2. O Caso do "Thue-Morse" (O Padrão Infinito)

Existe uma sequência famosa chamada Thue-Morse, que é gerada por uma regra simples de "troca e inversão" (começa com 0, vira 01, vira 0110, vira 01101001...). É uma sequência que parece aleatória, mas é totalmente previsível.

• O Mistério: Quantas torres perfeitas (Dyck) existem dentro dessa sequência? E qual é a altura máxima delas?
• A Solução: Os autores usaram um "robô matemático" chamado Walnut (um software que prova teoremas automaticamente) para mapear tudo.
  • Eles descobriram que as torres perfeitas dentro do Thue-Morse são muito limitadas: a altura máxima é sempre 2. Não importa o quanto você olhe, nunca encontrará uma torre de 3 andares perfeita nesse padrão específico.
  • Eles também criaram uma "fórmula mágica" (uma representação linear) para contar exatamente quantas torres de tamanho $2n$ existem. É como ter uma calculadora que diz: "Para uma torre de 100 blocos, existem exatamente X possibilidades".

3. A Ferramenta Mágica: Walnut

Os autores não fizeram isso apenas com lápis e papel. Eles usaram o Walnut, que é como um "Google" para sequências automáticas.

• Como funciona: Você diz ao computador: "Procure por qualquer sequência onde o número de bases seja igual ao de tampas e onde nunca haja uma tampa solta". O computador varre bilhões de possibilidades em segundos e diz: "Sim, existe" ou "Não, nunca".
• Isso permitiu que eles provassem coisas que seriam impossíveis de verificar manualmente, como a existência de torres infinitas em outras sequências.

4. Outras Sequências (Fibonacci e Rudin-Shapiro)

Eles também olharam para outras sequências famosas:

• Sequência de Fibonacci: É muito restritiva. Só existem torres perfeitas muito pequenas (de 2 e 4 blocos). É como se a sequência de Fibonacci fosse um terreno muito acidentado onde só cabem casinhas pequenas.
• Sequência de Rudin-Shapiro: Aqui, a história é diferente! Eles provaram que, dentro dessa sequência, existem torres perfeitas de qualquer altura. Você pode construir uma torre de 1000 andares, e ela estará escondida lá dentro. É como se essa sequência fosse um terreno plano e infinito, perfeito para arranha-céus.

Resumo Final

Este artigo é sobre encontrar padrões de equilíbrio (torres perfeitas) dentro de padrões de repetição (sequências infinitas).

• A lição principal: Se você impedir que uma sequência repita padrões demais (regra 7/3), você limita a complexidade das estruturas equilibradas que podem se formar dentro dela.
• A ferramenta: O uso de computadores para provar regras matemáticas complexas (como o Walnut) está revolucionando como entendemos esses padrões invisíveis.

Em suma, os autores nos mostraram que, mesmo em sequências infinitas e complexas, a matemática impõe limites rígidos sobre o quão "profundo" podemos mergulhar em estruturas de equilíbrio, a menos que você relaxe as regras de repetição.

Resumo técnico

Aqui está um resumo técnico detalhado do artigo "Dyck words, pattern avoidance, and automatic sequences" (Palavras de Dyck, evitação de padrões e sequências automáticas), de Lucas Mol, Narad Rampersad e Jeffrey Shallit, publicado em Communications in Mathematics (2025).

1. Problema e Contexto

O artigo investiga as propriedades das palavras de Dyck (sequências de parênteses balanceados, onde '0' é uma abertura e '1' é um fechamento) que aparecem como fatores (subsequências contíguas) em sequências binárias infinitas. O foco principal recai sobre três aspectos inter-relacionados:

• Evitação de Padrões: A relação entre a estrutura de palavras de Dyck e a ausência de potências (repetições) em sequências binárias.
• Sequências Automáticas: A caracterização e contagem de fatores de Dyck em sequências geradas por autômatos finitos, especificamente a Sequência de Thue-Morse.
• Limites de Nível de Aninhamento: Determinar se o nível de aninhamento (profundidade de parênteses) de palavras de Dyck em certas sequências é limitado ou não.

O trabalho utiliza ferramentas teóricas da teoria das palavras e combinações, apoiadas fortemente pelo provador de teoremas Walnut, que permite verificar propriedades de sequências automáticas via lógica de primeira ordem.

2. Metodologia

Os autores empregam uma abordagem híbrida que combina:

• Construções Morfismas: Definição de morfismos (regras de substituição) para gerar sequências com propriedades específicas de evitação de potências e estrutura de Dyck.
• Teoria de Sequências Automáticas e Regulares: Uso de autômatos finitos com saída (DFAO) e representações lineares para analisar sequências de contagem.
• Prova Assistida por Computador (Walnut): O uso do sistema Walnut para:
  • Provar rigorosamente a ausência de certas potências (ex: $7/3$-livre).
  • Construir autômatos que reconhecem fatores de Dyck e seus níveis de aninhamento.
  • Derivar representações lineares para sequências de contagem.
  • Verificar identidades recursivas e limites assintóticos.

3. Contribuições e Resultados Principais

A. Evitação de Potências e Nível de Aninhamento

• Teorema 2.1: O artigo prova que qualquer palavra binária que seja **$7/3$-livre de potências** (não contém potências de expoente$\ge 7/3$) e seja uma palavra de Dyck possui um nível de aninhamento no máximo 3.
• Otimização do Expoente: Os autores demonstram que este limite é o melhor possível para o expoente $7/3$. Para expoentes maiores (especificamente$7/3^+$), existem palavras de Dyck de **qualquer nível de aninhamento** que são livres de potências maiores que$7/3$.
• Construção: Eles fornecem uma construção explícita usando morfismos $g$ (sobre um alfabeto ternário) e $f$ (sobre binário) para gerar palavras de Dyck com níveis de aninhamento arbitrariamente grandes ($2t+2$) que são$7/3^+$-livres.

B. Caracterização na Sequência de Thue-Morse

• Teorema 3.1: Os autores caracterizam completamente os fatores de Dyck da Sequência de Thue-Morse ($t$). Eles provam que um fator de $t$ é uma palavra de Dyck se e somente se for da forma $h(x)$, onde $x$ é um fator de uma sequência auxiliar $s$ (fixo de um morfismo ternário) e $h$ é um morfismo específico definido no artigo.
• Limitação de Aninhamento: Como consequência, eles confirmam que o nível de aninhamento de qualquer fator de Dyck na Sequência de Thue-Morse é limitado a 2.

C. Contagem e Regularidade

• Sequências $k$-Regulares: O artigo estabelece que, para sequências automáticas que são "sincronizadas pela soma acumulada" (running-sum synchronized), o número de fatores de Dyck de comprimento $2n$, denotado por$d(n)$, forma uma sequência 2-regular.
• Representação Linear: Para a Sequência de Thue-Morse, os autores derivam uma representação linear de posto 7 para a sequência $d(n)$, permitindo o cálculo eficiente do número de fatores de Dyck para qualquer $n$.
• Tabela de Valores: Fornecem os primeiros valores de $d(n)$, identificando a sequência como A345199 na OEIS.

D. Limites Superiores e Inferiores para $d(n)$

• Teorema 5.2 (Limite Superior): Provas de que $d(n) \le n$ para todo $n \ge 1$. O limite é apertado (tight), pois $d(n) = n$ para $n = 3 \cdot 2^i$.
• Teorema 5.3 (Limite Inferior): Provas de que $d(n) \ge n/2$ para $n \ge 0$. O limite é atingido infinitamente frequentemente (ex: $d(2^i) = 2^{i-1}$ para $i \ge 2$).
• Valor Médio: O valor médio de $d(n)$ é assintoticamente $\frac{19}{24}n$.

E. Outras Sequências

• Palavras de Fibonacci e Period-Doubling: Mostram que o número de fatores de Dyck não vazios nessas sequências é muito limitado (apenas $01$,$0101$e, no caso do period-doubling, também$010101$).
• Sequência de Rudin-Shapiro: Demonstram que, diferentemente da Thue-Morse, a Sequência de Rudin-Shapiro contém fatores de Dyck de nível de aninhamento arbitrariamente grande. Além disso, provam que o conjunto dos comprimentos $n$ para os quais existem fatores de Dyck é um conjunto 4-automático.

4. Significado e Impacto

Este trabalho é significativo por várias razões:

1. Conexão entre Estrutura e Repetição: Estabelece limites rigorosos sobre como a restrição de evitar repetições (potências) afeta a complexidade estrutural (nível de aninhamento) de palavras de Dyck.
2. Aplicação de Walnut: Serve como um exemplo robusto de como provadores de teoremas automáticos podem ser usados para resolver problemas complexos de combinatória de palavras, incluindo a construção de autômatos para propriedades não triviais como o nível de aninhamento.
3. Análise Quantitativa: Fornece a primeira análise detalhada e quantitativa (contagem e limites) dos fatores de Dyck na Sequência de Thue-Morse, transformando uma propriedade qualitativa em dados numéricos precisos e sequências regulares.
4. Contraste entre Sequências: Destaca diferenças fundamentais entre sequências automáticas clássicas (Thue-Morse vs. Rudin-Shapiro) em relação à capacidade de suportar estruturas de parênteses profundas.

Em resumo, o artigo oferece uma compreensão profunda da interação entre a teoria das palavras de Dyck, a evitação de padrões e a teoria das sequências automáticas, utilizando uma combinação poderosa de provas matemáticas tradicionais e verificação computacional.