Dyck Words, Pattern Avoidance, and Automatic Sequences

Este artículo estudia las palabras de Dyck en secuencias binarias, demostrando que las palabras libres de potencias $7/3$ tienen un nivel de anidamiento acotado, caracterizando y contando los factores de la palabra de Thue-Morse que son de Dyck, y estableciendo cotas ajustadas para su número.

Lo esencial

¡Hola! Imagina que el lenguaje matemático es como un gran juego de construcción con bloques, pero en lugar de ladrillos, usamos dos tipos de piezas: 0 (que imaginaremos como un paréntesis de apertura () y 1 (un paréntesis de cierre )).

El artículo que vamos a explorar es como un manual de instrucciones para entender cómo se comportan estas piezas cuando se mezclan en secuencias infinitas y misteriosas. Los autores (Lucas Mol, Narad Rampersad y Jeffrey Shallit) son como detectives que usan una "lupa" matemática muy potente llamada Walnut para resolver estos misterios.

Aquí tienes la explicación de sus descubrimientos, contada como una historia:

1. El Juego de los Paréntesis Perfectos (Palabras de Dyck)

Primero, definan qué es una "palabra de Dyck". Imagina que tienes una cadena de paréntesis. Para que sea válida (una palabra de Dyck), debe estar perfectamente equilibrada:

• Cada ( debe tener su ) correspondiente.
• Nunca puedes cerrar un paréntesis antes de abrirlo (no puedes tener )().

Ejemplo: 010011 es válido: ( () ).
Ejemplo: 0110 es inválido: ())( (el segundo cierre no tiene su apertura).

El nivel de anidamiento es lo profundo que llega el juego. Si tienes ((())), el nivel es 3. Si tienes ()(), el nivel es 1.

2. El Límite de la Repetición (La Regla de 7/3)

Los autores se preguntaron: ¿Qué pasa si prohibimos que las palabras se repitan demasiado?
Imagina que tienes una regla estricta: "No puedes repetir una secuencia más de 2.33 veces (7/3)".

• El descubrimiento: Si sigues esta regla estricta, ¡el nivel de anidamiento de tus paréntesis nunca puede ser muy profundo! Se queda limitado a un máximo de 3 niveles. Es como si la prohibición de repetirte te impidiera construir torres muy altas; la estructura se colapsa si intentas hacerla muy compleja.
• La excepción: Si permitimos repeticiones un poco más grandes (más de 2.33 veces), entonces sí podemos construir torres infinitamente altas.

3. El Secreto de la Secuencia de Thue-Morse

La Secuencia de Thue-Morse es una secuencia famosa en matemáticas que parece aleatoria pero sigue reglas muy estrictas. Es como un patrón de mosaico que nunca se repite exactamente igual.

• El hallazgo: Los autores descubrieron exactamente qué partes de esta secuencia son palabras de Dyck válidas. Es como si pudieran decirte: "Si buscas en este mosaico infinito, solo encontrarás bloques de paréntesis equilibrados de formas muy específicas".
• Contando los bloques: También aprendieron a contar cuántas de estas palabras válidas existen de cierto tamaño. Descubrieron que, aunque la secuencia es infinita, el número de palabras válidas de un tamaño dado sigue un patrón predecible y ordenado (como una receta de cocina matemática).
• La altura máxima: En la Secuencia de Thue-Morse, el nivel de anidamiento nunca supera 2. ¡Es una secuencia muy "plana" en cuanto a paréntesis!

4. La Máquina de Adivinanzas (Walnut)

¿Cómo saben todo esto? Usaron un software llamado Walnut.
Imagina a Walnut como un robot superinteligente que puede leer las reglas de la secuencia y probar millones de casos en segundos.

• Si le preguntas: "¿Existe una palabra de paréntesis válida de longitud 100 en esta secuencia?", el robot responde instantáneamente.
• Si le preguntas: "¿Pueden las torres de paréntesis crecer infinitamente aquí?", el robot puede decirte "Sí" o "No" y hasta dibujar el mapa de dónde ocurren.

5. Otros Mundos de Secuencias

Los autores no se detuvieron solo en la Secuencia de Thue-Morse. Miraron a otros "vecinos":

• La Secuencia de Fibonacci: Es como una secuencia de crecimiento natural (1, 1, 2, 3, 5...). Descubrieron que en este mundo, las palabras de paréntesis válidas son muy escasas. Solo existen dos tipos pequeños: 01 y 0101. ¡Es un mundo muy limitado para los paréntesis!
• La Secuencia de Rudin-Shapiro: Aquí ocurre algo mágico. A diferencia de la Secuencia de Thue-Morse, aquí sí se pueden construir torres de paréntesis infinitamente altas. ¡El nivel de anidamiento puede crecer sin límite!

En Resumen

Este artículo es como un mapa del tesoro para entender cómo se comportan los paréntesis en diferentes universos matemáticos.

1. Reglas estrictas de repetición limitan la altura de tus torres de paréntesis.
2. La Secuencia de Thue-Morse es un lugar ordenado donde las torres son bajas y fáciles de contar.
3. La Secuencia de Rudin-Shapiro es un lugar salvaje donde las torres pueden tocar el cielo.
4. Y todo esto lo descubrieron usando un robot matemático (Walnut) que verifica cada posibilidad para asegurarse de que la respuesta sea 100% correcta.

Es un trabajo que combina la belleza de los patrones, la lógica de la programación y la curiosidad de saber hasta dónde pueden llegar las estructuras que creamos con solo dos símbolos: 0 y 1.

Resumen técnico

Aquí tienes un resumen técnico detallado del artículo "Dyck words, pattern avoidance, and automatic sequences" (Palabras de Dyck, evitación de patrones y secuencias automáticas) de Lucas Mol, Narad Rampersad y Jeffrey Shallit, presentado en Communications in Mathematics (2025).

1. Introducción y Definiciones del Problema

El artículo investiga las propiedades de las palabras de Dyck dentro de secuencias binarias infinitas.

• Definición: Se considera el alfabeto $\Sigma_2 = \{0, 1\}$, donde el '0' actúa como paréntesis izquierdo y el '1' como paréntesis derecho. Una palabra es de Dyck si representa una cadena de paréntesis balanceados (ej. 010011 es Dyck; 0110 no lo es).
• Nivel de anidamiento ($N(x)$): Mide la profundidad máxima de los paréntesis anidados en una palabra de Dyck. Formalmente, $N(\epsilon)=0$, $N(0y1) = N(y)+1$, y $N(yz) = \max(N(y), N(z))$.
• Balance ($B(x)$): Definido como $|x|_0 - |x|_1$. Una palabra es de Dyck si y solo si $B(x)=0$ y el balance de todos sus prefijos es no negativo.
• Objetivo: Analizar la existencia, caracterización y conteo de factores de Dyck en secuencias automáticas y estudiar cómo la evitación de potencias (repeticiones) afecta al nivel de anidamiento.

2. Metodología

Los autores emplean una combinación de técnicas teóricas y herramientas computacionales avanzadas:

• Teoría de Palabras y Morfismos: Uso de morfismos (reglas de sustitución) para construir palabras con propiedades específicas (libres de potencias, nivel de anidamiento controlado).
• Teorema de Walnut: Utilizan el demostrador de teoremas Walnut, una herramienta basada en lógica de primer orden para secuencias automáticas. Walnut permite verificar propiedades complejas (como la evitación de potencias o la existencia de factores) mediante la construcción de autómatas finitos deterministas (DFAO) y fórmulas lógicas.
• Secuencias Sincronizadas: Introducen el concepto de "secuencia sincronizada por suma acumulada" (running-sum synchronized) para extender la aplicabilidad de los métodos automáticos a secuencias donde el balance de paréntesis juega un papel crucial.
• Representaciones Lineales: Utilizan la teoría de secuencias $k$-regulares para encontrar representaciones lineales que permitan calcular eficientemente el número de factores de Dyck.

3. Contribuciones Clave y Resultados

A. Evitación de Potencias y Nivel de Anidamiento

• Teorema 2.1: Demuestran que si una palabra binaria es libre de potencias $\ge 7/3$ (7/3-power-free) y es de Dyck, su nivel de anidamiento está acotado por 3.
• Optimalidad: Muestran que este límite es óptimo respecto al exponente. Existen palabras de Dyck libres de potencias $> 7/3$ (es decir, $7/3^+$-power-free) con cualquier nivel de anidamiento.
• Construcción: Presentan una construcción explícita utilizando morfismos $g$ (sobre alfabeto ternario) y $f$ (sobre binario) para generar palabras de Dyck con nivel de anidamiento $2t+2$que son libres de potencias$> 7/3$. La prueba de la ausencia de potencias se realiza mediante Walnut, requiriendo un cálculo intensivo (130 GB de RAM).

B. Factores de Dyck en la Secuencia de Thue-Morse

• Caracterización (Teorema 3.1): Identifican exactamente los factores de Dyck en la secuencia de Thue-Morse ($t$). Son exactamente las palabras de la forma $h(x)$, donde $x$ es un factor de una secuencia auxiliar $s$ (definida por un morfismo sobre $\Sigma_3$) y $h$ es un morfismo específico.
• Límite de Anidamiento: Confirman que el nivel de anidamiento de cualquier factor de Dyck en Thue-Morse es máximo 2.
• Conteo y Regularidad: Demuestran que la función $d(n)$, que cuenta el número de factores de Dyck de longitud $2n$ en Thue-Morse, es una secuencia 2-regular.
  • Proporcionan una representación lineal de rango 7 para calcular $d(n)$ eficientemente.
  • Calculan los primeros términos de la secuencia (OEIS A345199).

C. Cotas para $d(n)$

• Cota Superior (Teorema 5.2): $d(n) \le n$ para todo $n \ge 1$. La igualdad se alcanza cuando $n = 3 \cdot 2^i$.
• Cota Inferior (Teorema 5.3): $d(n) \ge n/2$ para todo $n \ge 0$. La cota es alcanzada infinitamente a menudo (ej. para $n=2^i$).
• Valor Promedio: El valor promedio de $d(n)$ crece linealmente, aproximadamente como $\frac{19}{24}n$.

D. Otras Secuencias Automáticas

• Secuencia de Fibonacci: Solo contiene dos factores de Dyck no vacíos: 01 y 0101.
• Secuencia de Duplicación de Período: Contiene 01, 0101 y 010101.
• Secuencia de Rudin-Shapiro:
  • Demuestran que contiene factores de Dyck de nivel de anidamiento arbitrariamente grande.
  • Establecen que el conjunto de longitudes $n$ para las cuales existen factores de Dyck es un conjunto 4-automático (y por tanto 2-automático).
  • Utilizan la sincronización de la suma acumulada en base 4 para aplicar Walnut a esta secuencia.

E. Conjetura

• Proponen una conjetura sobre la secuencia de plegado de papel (paperfolding sequence): tiene un factor de Dyck de longitud $n$ si y solo si $n$ es de la forma $2^k - 2^i$con$0 \le i < k$.

4. Significado e Impacto

Este trabajo es significativo por varias razones:

1. Límites de la Evitación de Patrones: Establece una frontera precisa entre la evitación de repeticiones y la complejidad estructural (nivel de anidamiento) en palabras de Dyck. Muestra que el umbral de $7/3$ es crítico para limitar la profundidad de anidamiento.
2. Aplicación de Herramientas Automáticas: Demuestra la potencia de los demostradores de teoremas automáticos (como Walnut) para resolver problemas combinatorios complejos que involucran secuencias infinitas y propiedades de balance, áreas donde los métodos manuales tradicionales son insuficientes.
3. Nuevas Clases de Secuencias: Introduce y explota la noción de "secuencias sincronizadas por suma acumulada" para extender el análisis de factores de Dyck a una clase más amplia de secuencias automáticas.
4. Análisis Cuantitativo: Proporciona herramientas exactas (representaciones lineales) para contar factores de Dyck en la secuencia de Thue-Morse, un problema fundamental en la teoría de palabras combinatorias.

En resumen, el artículo conecta la teoría de lenguajes formales, la teoría de números (secuencias automáticas) y la combinatoria de palabras, ofreciendo tanto resultados teóricos profundos como algoritmos prácticos para el análisis de estas estructuras.