🔢 mathematics

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

Este artículo establece que todo entero par positivo puede representarse como una suma de como máximo seis palabras de Dyck primitivas, con la excepción de un conjunto finito de enteros (incluyendo el 46, que requiere ocho) y el umbral eventual agudo de 848, al aprovechar una novedosa conexión entre los caminos de Dyck y la codificación de Motzkin para demostrar teoremas de elevación de dígitos y límites de generación.

Autores originales: Takayuki Kuriyama

Publicado 2026-07-28

📖 8 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Takayuki Kuriyama

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que eres un detective intentando resolver un tipo de acertijo numérico muy específico. En el mundo de las matemáticas, existe una rama llamada teoría aditiva de números, que plantea una pregunta simple pero complicada: ¿Se puede construir cada número en un determinado grupo sumando unos pocos números "bloques de construcción" especiales? Piensa en ello como un juego donde tienes un conjunto limitado de piezas de Lego y quieres saber si puedes construir todas las alturas de torre posibles usando solo esas piezas. A veces, podrías necesitar solo dos piezas; otras veces, podrás necesitar diez. El "orden" del juego es el número máximo de piezas que alguna vez necesitarás para construir cualquier torre.

Para jugar a este juego, los matemáticos en esta historia utilizan un conjunto de bloques de construcción muy específico. Estos bloques son números que, cuando se escriben en binario (el lenguaje de computación de 0s y 1s), parecen paréntesis perfectamente equilibrados. En matemáticas, estos se llaman palabras de Dyck. Por ejemplo, 1100 es una palabra de Dyck válida porque si tratas un 1 como un paso "arriba" y un 0 como un paso "abajo", la trayectoria sube dos veces y baja dos veces, sin caer nunca por debajo de la línea de partida. Los autores se centran en un subconjunto especial de estas llamadas primitivas, que son los bloques "atómicos" que no pueden descomponerse en pares equilibrados más pequeños. La gran pregunta que abordan es: ¿Cuál es el número máximo de estos bloques primitivos que necesitas sumar para crear cualquier número par?

Este artículo es una clase magistral sobre cómo resolver este rompecabezas mezclando dos herramientas matemáticas diferentes. Los autores descubrieron que estos bloques binarios tienen una relación secreta con otro tipo de trayectoria llamada camino de Motzkin, que permite traducir el problema a un lenguaje diferente (base-4) donde es mucho más fácil de resolver. Demostraron que, si bien la mayoría de los números pares pueden construirse con un puñado de estos bloques, hay un pequeño y obstinado grupo de números que son mucho más difíciles de construir. Específicamente, encontraron que el número 46 es el caso más difícil, requiriendo ocho bloques, mientras que algunos otros necesitan siete. Sin embargo, también demostraron que una vez que pasas del número 848, nunca necesitarás más de seis bloques para construir cualquier número par. Es una historia de encontrar los "peores escenarios" en un vasto universo de números y demostrar exactamente dónde termina el caos y comienza el orden.

La historia de los equilibradores binarios

Sumerjámonos en la aventura. Los autores, liderados por Takayuki Kuriyama, están investigando un conjunto de números que provienen de un lenguaje de cadenas binarias equilibradas. Imagina que tienes una cadena de luces, algunas rojas (1) y algunas azules (0). Una "palabra de Dyck" es una cadena donde tienes el mismo número de luces rojas y azules, y si cuentas de izquierda a derecha, nunca tendrás más luces azules que rojas en ningún punto. Es como un baile donde no puedes salir del escenario hasta que hayas igualado cada paso arriba con un paso abajo.

Los autores están interesados en los bailarines "primitivos". Estos son las cadenas que solo regresan a la línea de salida (altura cero) al final mismo. Si una cadena regresa a cero a mitad de camino, es solo dos bailes más pequeños pegados, no uno primitivo. Tratan estas cadenas como números (leyéndolas como binario) y preguntan: ¿Cuántos de estos números primitivos necesitamos sumar para obtener cualquier número par?

El código secreto: De binario a base-4
El movimiento brillante en este artículo es darse cuenta de que estas cadenas binarias tienen una estructura oculta. Si agrupas los bits (00, 01, 10, 11), actúan como dígitos en un sistema de base-4 (0, 1, 2, 3). Los autores encontraron un mapa perfecto: cada número de Dyck primitivo (excepto el más pequeño, que es 2) corresponde a un número de base-4 que comienza con un 3, termina con un 0 y tiene una palabra "Motzkin" en el medio.

Piensa en una palabra de Motzkin como una trayectoria que puede subir, bajar o mantenerse plana, pero que nunca baja del suelo. Esta conexión es la "Piedra de Rosetta" del artículo. Permite a los autores traducir un problema difícil sobre complejas cadenas binarias a un problema más limpio sobre números de base-4 y estas trayectorias de paso plano. Esta traducción revela que el conjunto de números que estudian es "digitalmente cerrado", lo que significa que si tienes un número en el conjunto, a menudo puedes generar nuevos números añadiendo dígitos específicos.

La estrategia de dos vías
Para resolver el rompecabezas, los autores utilizan un ataque astuto de dos vías, tratando los números pares según cómo se comportan cuando se dividen por 4.

La vía "fácil" (múltiplos de 4): Para los números que son perfectamente divisibles por 4, los autores utilizan una "subaproximación regular". Esto es una forma elegante de decir que encontraron un subconjunto más simple y predecible de los números que es fácil de manejar. Demostraron que este conjunto más simple es lo suficientemente poderoso como para construir todos los múltiplos grandes de 4 usando solo seis bloques.
La vía "difícil" (números que son 2 mod 4): Para los números que dejan un resto de 2 cuando se dividen por 4 (como 6, 10, 14), el conjunto más simple no es suficiente. Aquí, utilizan todo el poder de la familia "codificada por Motzkin". Demostraron que esta familia más grande y compleja puede construir estos números usando solo cinco bloques.

La magia del "levantamiento"
¿Cómo saben que esto funciona para todos los números grandes, no solo para los que revisaron? Utilizan una técnica llamada levantamiento de dígitos (digit lifting). Imagina que tienes una pequeña escalera que puede alcanzar cierta altura. Los autores demostraron un teorema que dice: si puedes construir un rango continuo de números con un cierto número de bloques, puedes "levantar" esa capacidad para construir todos los números más grandes simplemente añadiendo dígitos específicos a los extremos de los bloques. Es como tener una regla mágica que dice: "Si puedes construir una torre de altura 100, puedes construir automáticamente torres de altura 400, 401, 402, y así sucesivamente". Esto les permite tomar una lista finita de números verificados y demostrar que el patrón se mantiene para siempre.

Los resultados: Los números obstinados
Después de establecer sus herramientas, los autores se pusieron manos a la obra clasificando las excepciones. Descubrieron que, aunque la mayoría de los números pares son fáciles de construir, hay una lista específica de números "obstinados" que requieren más de seis bloques.

El campeón de la dificultad: El número 46 es el más difícil de todos. No puede construirse con siete o menos bloques; requiere estrictamente ocho.
Los segundos puestos: Hay otros diez números que necesitan siete bloques: 34, 44, 98, 154, 198, 202, 206, 838, 842 y 846.
El umbral: Los autores demostraron que 848 es el número mágico. Cada número par desde 848 en adelante puede construirse con seis o menos bloques.

No solo adivinaron estos números; utilizaron cálculos computacionales exactos para verificar cada caso hasta el umbral y usaron sus pruebas matemáticas para mostrar que esto se mantiene para el infinito.

Por qué esto es importante
Este artículo es un hermoso ejemplo de cómo diferentes áreas de las matemáticas —la informática (lenguajes y autómatas), la combinatoria (trayectorias y árboles) y la teoría de números (suma)— pueden bailar juntas. Los autores no solo encontraron una lista de números; construyeron un marco de trabajo. Mostraron que incluso para un conjunto de números definido por un patrón complejo y no repetitivo (un lenguaje "independiente del contexto"), puedes encontrar un patrón simple y repetitivo (un lenguaje "regular") que cubra la mayor parte del terreno, y luego usar la complejidad total para llenar los huecos.

También descubrieron que el "orden" del juego cambia dependiendo de las reglas. Si solo miras los múltiplos de 4, solo necesitas 5 bloques. Pero si incluyes los números que son 2 mod 4, el requisito salta a 6. Y si miras el peor escenario absoluto (incluyendo el número 46), necesitas 8.

Al final, el artículo nos da un mapa completo. Sabemos exactamente qué números son los problemáticos, sabemos el límite exacto donde termina el problema y tenemos un algoritmo constructivo (una receta paso a paso) para construir cualquier número par grande usando estos bloques binarios especiales. Convierte un problema de apariencia caótica en un sistema perfectamente ordenado, demostrando que incluso en el mundo de los números abstractos, siempre hay un patrón esperando ser encontrado.

Resumen Técnico: Bases Aditivas a partir de Palabras de Dyck Primitivas

Planteamiento del Problema
Este artículo investiga las representaciones aditivas de los enteros pares positivos utilizando sumandos extraídos del conjunto $N_pD$ . Este conjunto consiste en el cero y los valores enteros de palabras de Dyck primitivas interpretadas como números binarios. Una palabra de Dyck es una secuencia balanceada de 1s (pasos ascendentes) y 0s (pasos descendentes); una palabra es primitiva si su trayectoria asociada regresa a la altura cero solo al final. La cuestión central es determinar el orden aditivo de este conjunto: específicamente, el menor entero $h$ tal que cada entero par suficientemente grande puede expresarse como una suma de a lo sumo $h$ elementos de $N_pD$ , y clasificar el conjunto exacto de enteros "excepcionales" que requieren más de un número dado de sumandos.

Metodología
Los autores emplean un enfoque híbrido que combina la teoría de lenguajes formales, la teoría de números combinatoria y algoritmos constructivos:

Codificación de Bloques Posicionales: La idea estructural central es una biyección entre las palabras de Dyck primitivas y las palabras de Motzkin de dos colores mediante una codificación de bloques en base 4. Al emparejar dígitos binarios consecutivos, los autores mapean las palabras de Dyck primitivas (excluyendo la palabra "10") a palabras en base 4 de la forma $3w0$ , donde $w$ es una palabra de Motzkin de dos colores. Esto permite a los autores traducir el lenguaje no regular de Dyck hacia una estructura compatible con la aritmética posicional en base 4.
Subaproximación Regular: Para manejar enteros congruentes con $0 \pmod 4$ , los autores construyen una subaproximación regular explícita del lenguaje de Dyck primitivas. Este subconjunto, definido por la expresión regular $11(01|10)^*00$ , corresponde a palabras de Motzkin compuestas únicamente por los dígitos $\{1, 2\}$ . Este subconjunto regular es susceptible a métodos de autómatas finitos y proporciona una cobertura para los múltiplos de 4.
Levantamiento y Propagación de Dígitos por Intervalos: El artículo introduce un Teorema de Levantamiento de Dígitos por Intervalos. Este teorema demuestra que si un conjunto $A$ satisface una propiedad de clausura (específicamente $4A + \{1, 2\} \subseteq A$ ), un intervalo finito de números representables puede extenderse recursivamente a una cola infinita. Esto permite a los autores convertir certificados computacionales finitos (conjuntos suma de números pequeños) en pruebas de representabilidad para todos los enteros suficientemente grandes.
Certificados Finitos y Búsqueda Exhaustiva: La prueba se basa en el cálculo de conjuntos suma de generadores pequeños mediante aritmética de enteros exacta. Los autores verifican intervalos específicos donde los conjuntos suma de la familia regular (para múltiplos de 4) y la familia codificada por Motzkin (para enteros $\equiv 2 \pmod 4$ ) se solapan suficientemente para activar la propagación del levantamiento de dígitos.

Contribuciones Clave

Caracterización Exacta en Base 4: El artículo establece la identidad $DP = \{10\} \cup \phi(3 \cdot \text{Motz} \cdot 0)$ , donde $\phi$ es un morfismo uniforme que mapea dígitos en base 4 a pares binarios. Esto proporciona un vínculo estructural preciso entre las palabras de Dyck primitivas y las trayectorias de Motzkin que preserva los valores posicionales canónicos.
Clasificación de Enteros Excepcionales: Los autores clasifican completamente los enteros pares positivos que requieren más de seis sumandos.
- El entero 46 es el único entero par que requiere ocho sumandos.
- Los enteros 34, 44, 98, 154, 198, 202, 206, 838, 842 y 846 requieren exactamente siete sumandos.
- Cualquier otro entero par requiere a lo sumo seis.
Umbrales Agudos: El artículo identifica el 848 como el umbral eventual agudo: todo entero par $N \ge 848$ es una suma de a lo sumo seis números de Dyck primitivos.
Análisis del Orden Asintótico: Los autores distinguen entre el "orden relativo" (para todos los enteros pares) y el "orden asintótico" (para enteros suficientemente grandes).
- El conjunto $N_pD$ es una base aditiva relativa de orden 8 para los enteros pares (debido a la excepción en 46).
- El orden asintótico relativo es 6.
- La familia "dividida por la mitad" $P$ (donde $N_pD = \{0, 2\} \cup 4P$ ) tiene un orden aditivo asintótico de 5.
Algoritmos Constructivos: El mecanismo de levantamiento de dígitos genera un algoritmo constructivo que produce representaciones para enteros grandes en $O(\log n)$ etapas recursivas, convirtiendo representaciones de semillas finitas en colas infinitas.

Resultos y Significado
El artículo demuestra que, aunque el lenguaje de las palabras de Dyck primitivas es determinista de contexto libre (y, por lo tanto, no es regular), sus propiedades aditivas pueden analizarse eficazmente separando el problema en clases de residuos módulo 4.

Para $N \equiv 0 \pmod 4$ , una subaproximación regular es suficiente para demostrar que seis sumandos son eventualmente suficientes.
Para $N \equiv 2 \pmod 4$ , la prueba requiere todo el poder de la familia codificada por Motzkin y una cobertura de cinco sumandos, lo que, combinado con la necesidad de usar un número impar del sumando '2', eleva el límite asintótico a seis.

La importancia del trabajo radica en su aplicación exitosa de subaproximaciones regulares a un lenguaje no regular para resolver un problema de teoría de números aditiva. Proporciona un ejemplo concreto de cómo la interacción entre la estructura del lenguaje formal (Dyck vs. Motzkin) y los sistemas de numeración posicional produce límites computables y agudos. Los autores señalan explícitamente que el límite de seis es asintóticamente óptimo, ya que la secuencia $N_k = 10 \cdot 4^{k+1} - 6$ requiere exactamente seis sumandos para cada $k \ge 2$ .

Todos los certificados finitos y la clasificación de los valores excepcionales son verificados por programas complementarios utilizando aritmética de enteros exacta, asegurando la reproducibilidad de los resultados. El artículo concluye que 848 es el menor entero par tal que todos los enteros pares mayores son representables por a lo sumo seis números de Dyck primitivos, mientras que 46 sigue siendo la única excepción que requiere ocho.

La historia de los equilibradores binarios

Más como este