The Thue-Morse Transform

Este artículo introduce la transformada de Thue-Morse, demostrando que sus iteraciones sobre la secuencia clásica generan nuevas familias de soluciones al problema de Prouhet-Tarry-Escott, estableciendo ecuaciones funcionales para números "malvados" y "odiosos" generalizados, determinando su complejidad factorial y proponiendo extensiones a sistemas d-arios y de Fibonacci.

Lo esencial

Imagina que tienes un juego de bloques de construcción, pero en lugar de ladrillos, usas ceros y unos (0 y 1). La mayoría de la gente conoce una secuencia famosa llamada "Thue-Morse", que es como un patrón de bloques que nunca se repite exactamente igual y tiene reglas muy estrictas para cambiar de color.

Este artículo, escrito por Benoît Cloitre, no solo estudia ese patrón clásico, sino que inventa una "máquina mágica" (a la que llama Transformada Thue-Morse) que toma ese patrón y lo transforma una y otra vez, creando una torre de nuevos patrones, cada uno más complejo que el anterior.

Aquí te explico los conceptos clave usando analogías sencillas:

1. La Máquina de Transformación (El "Tamiz")

Imagina que tienes una fila infinita de casillas, algunas pintadas de negro (0) y otras de blanco (1).

• La máquina mira la fila y dice: "¡Oye! Las casillas negras están en las posiciones 0, 3, 5... y las blancas en 1, 2, 4...".
• Luego, la máquina hace algo curioso: toma esas posiciones y las usa para crear una nueva fila.
  • Si la posición original era negra, la nueva fila pone un 0.
  • Si era blanca, pone un 1.
  • Pero espera, hay un truco: la máquina invierte los colores en ciertas posiciones basándose en un "código secreto".

Si haces esto una vez, obtienes una nueva secuencia. Si lo haces de nuevo sobre la nueva secuencia, obtienes otra. Si lo repites muchas veces, construyes una torre de secuencias. El artículo descubre que esta torre no es un caos; tiene una estructura matemática muy limpia, como si cada nivel de la torre tuviera su propia "máscara" o filtro que decide qué bits (0s y 1s) importan.

2. El Problema de la "Equidad Matemática" (Prouhet-Tarry-Escott)

¿Alguna vez has intentado dividir un grupo de personas en dos equipos para que la suma de sus edades sea igual? O la suma de sus alturas al cuadrado? Eso es difícil.

Los matemáticos llevan siglos buscando formas de dividir números en dos grupos (llamémoslos "Equipo A" y "Equipo B") de tal manera que:

• La suma de los números sea igual.
• La suma de los números al cuadrado sea igual.
• La suma de los números al cubo sea igual... y así sucesivamente.

El artículo demuestra que cada nivel de nuestra Torre Mágica es una solución perfecta para este problema.

• Nivel 0 (El clásico): Divide los números de forma que las sumas sean iguales hasta cierto punto.
• Nivel 1, 2, 3... (Los nuevos): Cada vez que subes un nivel en la torre, la máquina te permite hacer divisiones donde las sumas son iguales para potencias mucho más altas. Es como si cada nueva secuencia fuera un "super-árbitro" capaz de equilibrar cuentas mucho más complejas que el árbitro anterior.

3. Los "Números Malvados" y "Números Perversos" (Evil y Odious)

En matemáticas, a los números que tienen un número par de unos en su código binario se les llama "malvados" (evil) y a los que tienen un número impar se les llama "perversos" (odious).

• En el juego clásico, si tomas un número "malvado" y lo transformas, obtienes otro "malvado" de una forma muy predecible (como multiplicar por 2).
• La gran novedad: Cuando aplicamos nuestra máquina mágica a los niveles superiores de la torre, estas reglas de transformación se vuelven más ricas. Ya no son simples multiplicaciones; ahora tienen "correcciones" que siguen un patrón automático pero más complejo. Es como si el juego de "malvados y perversos" tuviera reglas nuevas y más sofisticadas en cada piso de la torre.

4. La Estructura de la Torre (Máscaras Binarias)

El artículo descubre que no necesitas construir la torre paso a paso para saber qué hay en el nivel 100. Hay una fórmula directa, como una máscara de bits.
Imagina que cada nivel de la torre tiene una "máscara" (un número en binario). Esta máscara actúa como un filtro de gafas de sol:

• Si la máscara tiene un "0" en una posición, esa posición del número original cuenta.
• Si tiene un "1", esa posición se ignora.
  El resultado final es simplemente la suma (paridad) de los bits que pasaron el filtro. Esto convierte un proceso infinito y complicado en una operación de "filtrado" muy sencilla.

5. Más allá de lo binario (El mundo de los Fichas y la Fibonaccis)

El autor no se queda solo en el mundo de los 0 y 1.

• Versión Multicolor: Imagina que en lugar de solo negro y blanco, tienes 3, 4 o 10 colores. La máquina funciona igual, creando divisiones equitativas en sistemas de numeración más complejos.
• Versión Fibonacci: Imagina un sistema donde los números se construyen como la famosa secuencia de Fibonacci (1, 1, 2, 3, 5...). El autor prueba que si usas esta secuencia como base, la máquina también funciona, creando un "espejo" de la torre original, aunque con reglas un poco más suaves (no es tan perfecto como en el caso binario, pero sigue siendo elegante).

En Resumen

Este artículo es como descubrir que detrás de un simple juego de cambiar colores (0 y 1), existe una fábrica infinita de estructuras matemáticas.

1. Crea una torre de patrones donde cada piso es una nueva versión del clásico.
2. Cada piso resuelve problemas de equilibrio (sumas de potencias) cada vez más difíciles.
3. Tiene reglas de transformación que se vuelven más ricas y complejas en cada nivel.
4. Y lo mejor: todo esto se puede describir con una fórmula simple de máscaras, revelando que el caos aparente es, en realidad, una arquitectura perfectamente ordenada.

Es un viaje desde un simple patrón de ceros y unos hasta un universo de soluciones matemáticas elegantes, demostrando que a veces, la repetición de un proceso simple puede generar una complejidad hermosa y útil.

Resumen técnico

A continuación presento un resumen técnico detallado del artículo "The Thue–Morse Transform" de Benoît Cloitre, estructurado según los puntos solicitados.

1. El Problema y el Contexto

El punto de partida de la investigación no es una secuencia binaria aislada, sino un operador definido sobre secuencias binarias: la Transformada de Thue-Morse (TM).

• Contexto Histórico: El problema se enmarca en la teoría de números combinatoria, específicamente en el Problema de Prouhet-Tarry-Escott (PTE). Este problema busca particionar un conjunto de enteros en subconjuntos tales que las sumas de sus potencias sean iguales hasta un cierto grado $k$. La construcción clásica de Prouhet (1851) utiliza la paridad de la suma de dígitos en base $d$ (específicamente la secuencia de Thue-Morse en base 2) para generar soluciones ideales.
• La Pregunta Central: ¿Qué ocurre si se aplica iterativamente la transformada de Thue-Morse a la propia secuencia de Thue-Morse? ¿Existe una estructura aritmética subyacente en esta "torre" de secuencias iteradas?
• Objetivo: Definir explícitamente esta torre de secuencias, caracterizar su estructura aritmética, generalizar las identidades de composición de los números "malvados" (evil) y "perversos" (odious), y determinar su complejidad de factores.

2. Metodología

El autor emplea una combinación de teoría de números, combinatoria de palabras y teoría de secuencias automáticas.

• Definición del Operador: Se define la transformada $T(\sigma)$ para una secuencia binaria $\sigma$. Dado que $\sigma$ tiene infinitos ceros y unos, se definen dos subsecuencias complementarias:
  • $v_\sigma(n)$: posiciones de los ceros (números "malvados").
  • $u_\sigma(n)$: posiciones de los unos (números "perversos").
    La nueva secuencia $\tau = T(\sigma)$ se define recursivamente basándose en estas posiciones: $\tau(v_\sigma(n)) = \tau(n)$ y $\tau(u_\sigma(n)) = 1 - \tau(n)$.
• Iteración: Se construye una torre de secuencias comenzando con la secuencia clásica de Thue-Morse ($a_0 = t$) y definiendo $a_{m+1} = T(a_m)$.
• Herramientas Analíticas:
  • Máscaras de Bits: Uso de operaciones lógicas (AND, XOR) sobre la expansión binaria de los índices para encontrar una fórmula cerrada.
  • Funciones Generadoras: Generalización de la prueba de Borwein e Ingalls para demostrar identidades de sumas de potencias iguales.
  • Desustitución: Análisis de la complejidad de factores mediante el estudio de la "secuencia derivada" (diferencia XOR de términos adyacentes).
  • Generalización: Extensión a bases $d$ (sistema $d$-ario) y a sistemas de numeración no dyádicos (Zeckendorf/Fibonacci).

3. Contribuciones Clave y Resultados Principales

A. Fórmula Explícita de la Torre Iterada

El resultado estructural más importante es la identificación de la $m$-ésima iteración $a_m(n)$ mediante una fórmula de máscara de bits:
$$a_m(n) = \bigoplus_{p \ge 0, \, p \ \& \ m = 0} b_p(n)$$
Donde $b_p(n)$ es el $p$-ésimo bit de $n$ en base 2, $\&$ es el AND bit a bit y $\oplus$ es la suma módulo 2 (XOR).

• Significado: La secuencia $a_m(n)$ es la paridad de los bits de $n$ cuyas posiciones no están en la "soporte" binario de $m$. Esto proporciona una descripción cerrada y aritmética de toda la torre, eliminando la necesidad de definiciones recursivas complejas.

B. Soluciones Generalizadas al Problema PTE

El artículo demuestra que cada nivel $m$ de la torre genera nuevas familias de soluciones al problema PTE.

• Teorema 4.2: Para un nivel $m$ y un intervalo de longitud $N = B(m) \cdot L$, la partición inducida por $a_m$ iguala las sumas de potencias hasta el grado $s_m L - 1$, donde $s_m$ es el número de posiciones de bits seleccionadas por la máscara $m$ en un periodo.
• Innovación: A diferencia de las construcciones clásicas que solo aumentan el grado mediante la longitud del intervalo, aquí el grado se controla mediante el parámetro de máscara $m$, permitiendo grados más altos con intervalos más cortos o estructuras más ricas.

C. Números Generalizados Malvados y Perversos

Se estudian las secuencias de posiciones de ceros ($v_m$) y unos ($u_m$) para cada nivel $m$.

• Ecuaciones Funcionales: Se prueban ecuaciones de composición para $u_m$ y $v_m$. Mientras que en el caso clásico ($m=0$) las correcciones son constantes (0 o 1), para $m > 0$ las correcciones son secuencias automáticas no triviales ($c_m(n)$).
• Interacción entre Niveles: Se establecen ecuaciones funcionales cruzadas (entre diferentes niveles $m$ y $m'$), revelando que la estructura de corrección depende de la paridad de $m$ y de la interacción de las máscaras.

D. Complejidad de Factores (Mersenne Levels)

Para los niveles donde $m = 2^k - 1$ (niveles de Mersenne), se determina completamente la complejidad de factores $p_{a_m}(n)$ (número de subpalabras distintas de longitud $n$).

• Regímenes Lineales y Pieza por Pieza: Se prueba que existe un régimen lineal inicial exacto ($p(n) = 2n$) hasta $n = B(m) + 1$.
• Fórmula Jerárquica: Mediante un argumento de desustitución sobre la secuencia derivada, se establece una fórmula exacta y pieza por pieza para todo $n$, mostrando una estructura fractal jerárquica con fases de crecimiento y mesetas.

E. Extensiones Más Allá de la Semilla Clásica

El autor explora la aplicabilidad de la transformada más allá de la secuencia de Thue-Morse estándar:

1. Generalización $d$-aria: Se extiende la construcción a bases $d$ arbitrarias, recuperando el teorema de Prouhet clásico y generando nuevas familias de soluciones.
2. Secuencia Meta-Thue-Morse ($M_2$): Se muestra que secuencias automáticas más complejas (como $M_2$) también admiten una estructura de máscaras y generan familias PTE.
3. Análogo de Fibonacci: Se aplica la transformada a la secuencia de Thue-Morse-Fibonacci (basada en la numeración Zeckendorf). Aunque no se obtiene una torre con la misma estructura de máscaras simple, se descubren "sombras PTE" con defectos de grado 1 y 2 expresables mediante números de Fibonacci.

4. Significado e Impacto

• Unificación Conceptual: El trabajo unifica la teoría de secuencias automáticas, la teoría de números aditiva (problema PTE) y la combinatoria de palabras bajo un único operador iterativo.
• Nuevas Estructuras Aritméticas: La identificación de las correcciones automáticas no constantes en las composiciones de números malvados/perversos abre una nueva línea de investigación sobre la "sombra aritmética" de las iteraciones de transformadas.
• Optimización Combinatoria: La capacidad de controlar el grado de las soluciones PTE mediante máscaras de bits ofrece un nuevo mecanismo para construir particiones de enteros con propiedades de equilibrio de potencias, superando las limitaciones de las construcciones clásicas.
• Fundamento para Futuras Investigaciones: El artículo plantea problemas abiertos cruciales, como el desarrollo de la teoría de composición en base $d \ge 3$ y la caracterización de qué otras secuencias automáticas o estirianas poseen órbitas de transformada TM estructuradas.

En resumen, Benoît Cloitre presenta una generalización profunda y explícita de la secuencia de Thue-Morse, transformando un objeto clásico en una familia infinita de secuencias con estructuras aritméticas ricas, soluciones optimizadas para problemas de suma de potencias y complejidad combinatoria bien definida.