On a sequence of Kimberling and its relationship to the Tribonacci word

Este artículo demuestra las conjeturas de Clark Kimberling sobre su secuencia binaria definida por reglas de inflación, establece su relación con la palabra infinita de Tribonacci y determina su complejidad de subpalabras y exponente crítico, utilizando en parte el demostrador de teoremas Walnut.

Lo esencial

Imagina que tienes un juego de bloques de construcción mágicos. En 2017, un matemático llamado Clark Kimberling creó una secuencia infinita de ceros y unos (como un código de barras infinito: 0100101100...) siguiendo unas reglas muy específicas para "inflar" o estirar sus bloques. Kimberling hizo varias conjeturas (suposiciones inteligentes) sobre cómo crecía esta secuencia y qué secretos escondía, pero no pudo probarlas todas.

Este artículo es como una aventura de detectives donde tres investigadores (dos de la República Checa y uno de Canadá) usan herramientas modernas para resolver el misterio de Kimberling. Aquí te explico qué descubrieron, usando analogías sencillas:

1. El Misterio del Crecimiento (La Longitud)

Kimberling notó que cada vez que aplicaba sus reglas de inflación, la longitud de la secuencia crecía de una manera muy particular. Conjeturó que había una fórmula matemática exacta para predecir cuánto medía la secuencia en cada paso.

• La Analogía: Imagina que tienes una planta. Cada semana, la planta crece, pero no de forma aleatoria; sigue un patrón de crecimiento muy estricto. Kimberling dijo: "Apuesto a que la altura de la planta la semana $n$ es exactamente $X$".
• La Solución: Los autores usaron un "detective de lógica" llamado Walnut (un software que funciona como un juez infalible para problemas matemáticos) para verificar esto. ¡Ganaron la apuesta! Probaron que la fórmula de Kimberling era correcta y que la secuencia crece siguiendo un ritmo predecible, similar a cómo crecen las familias de conejos en la famosa sucesión de Fibonacci, pero con un toque más complejo (la sucesión de Tribonacci).

2. El Secreto de la Relación (El Espejo Tribonacci)

La parte más fascinante es que descubrieron que la secuencia de Kimberling no es un "extraño" aislado. Está íntimamente relacionada con una secuencia famosa llamada Palabra Tribonacci.

• La Analogía: Piensa en la Palabra Tribonacci como una canción original muy famosa. La secuencia de Kimberling es como una versión de cover de esa canción. No suena exactamente igual, pero si sabes cómo traducir las notas de la canción original, puedes entender perfectamente la versión de Kimberling.
• El Descubrimiento: Los autores demostraron que la secuencia de Kimberling es simplemente la Palabra Tribonacci "traducida" mediante un código secreto (una función matemática). Esto es crucial porque la Palabra Tribonacci ya estaba muy estudiada; al saber que son "primos hermanos", pudieron aplicar todo lo que ya sabían sobre la canción original para entender la nueva secuencia.

3. El Mapa y el Automata (El GPS)

Para estudiar la secuencia a fondo, construyeron un "mapa" o un automata (una máquina teórica simple).

• La Analogía: Imagina que quieres saber qué letra hay en la posición número 1,000,000 de esta secuencia infinita. Contar uno por uno sería imposible. El automata que construyeron es como un GPS de alta velocidad. Le das el número de la posición (escrito en un código especial llamado "representación Tribonacci") y el GPS te dice instantáneamente si es un 0 o un 1.
• Para qué sirve: Con este GPS, pudieron probar matemáticamente que la secuencia es "equilibrada" (no tiene demasiados ceros ni demasiados unos en ninguna parte) y que no tiene patrones repetitivos aburridos.

4. La Complejidad y el "Grito" Crítico

Finalmente, midieron dos cosas importantes sobre la secuencia:

1. Complejidad de Factores: ¿Cuántas combinaciones diferentes de bloques existen?
   • Analogía: Si la secuencia fuera un idioma, ¿cuántas palabras diferentes de 10 letras existen? Descubrieron que la secuencia de Kimberling es tan rica y variada que tiene el doble de combinaciones posibles que su longitud (una propiedad llamada "palabra de Rote"). Es un idioma muy complejo y rico.
2. Exponente Crítico: ¿Qué tan repetitiva es la secuencia? ¿Puede haber una parte que se repita muchas veces seguidas (como "000000...")?
   • Analogía: Imagina que la secuencia es una cinta de música. El "exponente crítico" es la medida de cuánto puede "gritar" o repetirse una nota antes de que deje de ser música y se vuelva ruido. Descubrieron que la secuencia de Kimberling tiene un límite de repetición muy específico (aproximadamente 3.19 veces), exactamente el mismo que la Palabra Tribonacci original.

En Resumen

Este paper es una historia de éxito donde:

1. Validaron las ideas de un aficionado (Kimberling) usando matemáticas rigurosas.
2. Conectaron dos mundos (la secuencia nueva y la Tribonacci) mostrando que son dos caras de la misma moneda.
3. Crearon herramientas (como el software Walnut y los autómatas) que actúan como lentes de aumento para ver patrones ocultos en secuencias infinitas.

Es un ejemplo perfecto de cómo las matemáticas modernas combinan la intuición humana con la potencia de la computación para desentrañar los secretos de los patrones que gobiernan nuestro universo.

Resumen técnico

Aquí presento un resumen técnico detallado del artículo "On a sequence of Kimberling and its relationship to the Tribonacci word" (Sobre una secuencia de Kimberling y su relación con la palabra Tribonacci), escrito por Lubomíra Dvořáková, Edita Pelantová y Jeffrey Shallit.

1. El Problema

En 2017, Clark Kimberling definió una secuencia binaria infinita $B$ (OEIS A288462) mediante reglas de inflación no estándar. La secuencia se genera a partir de $B_0 = 00$ aplicando iterativamente reglas de sustitución sobre bloques máximos de la forma $00$,$0$y$1$:

• $00 \mapsto 0101$
• $0 \mapsto 0$
• $1 \mapsto 10$

Kimberling formuló varias conjeturas sobre esta secuencia, incluyendo:

1. La fórmula para la longitud de las iteraciones $|B_i|$.
2. La relación asintótica entre los índices de las ocurrencias de $0$y$1$en$B$ y constantes específicas.
3. Propiedades de complejidad y exponente crítico que no habían sido probadas rigurosamente.

El desafío principal radica en que las reglas de inflación no son morfismos simples (la sustitución depende del contexto de los bloques), lo que dificulta el análisis combinatorio tradicional.

2. Metodología

Los autores emplean una combinación de técnicas de teoría de autómatas, combinatoria sobre palabras y demostración automática de teoremas.

• Demostración Automática (Walnut): Utilizan el demostrador de teoremas Walnut, que trabaja con lógica de primer orden sobre secuencias automáticas. Para ello, construyen un Autómata Finito Determinista con Salida (DFAO) que calcula el $n$-ésimo símbolo de la secuencia $B$. La entrada al autómata es la representación de $n$ en base Tribonacci.
• Relación con la Palabra Tribonacci: Establecen una conexión estructural profunda entre $B$ y la palabra Tribonacci infinita ($TR$), que es el punto fijo del morfismo $0 \to 01$,$1 \to 02$,$2 \to 0$.
• Análisis de Factores Bispeciales: Para determinar la complejidad de factores y el exponente crítico, analizan los "factores bispeciales" (palabras que pueden extenderse a la izquierda y derecha con ambos símbolos del alfabeto) y sus "palabras de retorno" (las subpalabras mínimas que conectan dos ocurrencias consecutivas de un factor).

3. Contribuciones Clave y Resultados

A. Prueba de las Conjeturas de Kimberling sobre Longitudes

Demuestran que la longitud de la $i$-ésima iteración, $|B_i|$, sigue la recurrencia definida por Kimberling:
$$c_i = 2c_{i-1} - c_{i-4} \quad \text{para } i \ge 4$$
con condiciones iniciales $c_0=2, c_1=4, c_2=6, c_3=10$. La prueba se basa en descomponer la secuencia en bloques de retorno y demostrar que las cuentas de estos bloques satisfacen una relación lineal que conduce a la misma recurrencia.

B. Relación con la Palabra Tribonacci

El resultado central es el Teorema 2, que establece que la secuencia de Kimberling $B$ es la imagen de la palabra Tribonacci $TR$ bajo un morfismo específico, precedido por un $0$:
$$B = 0 \cdot f(TR)$$
donde $f: 0 \mapsto 10, 1 \mapsto 0, 2 \mapsto 1$.
Esto permite construir el autómata para $B$ utilizando las propiedades conocidas de $TR$ y sus representaciones en base Tribonacci.

C. Balance de la Secuencia

Utilizando Walnut, prueban que la secuencia $B$ es 3-balanceada pero no 2-balanceada. Esto significa que para cualquier dos factores de la misma longitud, la diferencia en el número de unos es como máximo 3.

D. Índices de Ocurrencia (Conjeturas A288463 y A288464)

Refinan las conjeturas de Kimberling sobre los índices de las $n$-ésimas ocurrencias de $0$($I_0(n)$) y$1$($I_1(n)$):

• $I_0(n) \approx \psi n$, donde $\psi \approx 1.839286$ es la constante Tribonacci.
• $I_1(n) \approx \gamma n$, donde $\gamma = (\psi^2 + 1)/2 \approx 2.191487$.
  Los autores prueban desigualdades precisas:
  $$\lfloor \psi n \rfloor - 2 \le I_0(n) \le \lfloor \psi n \rfloor + 2$$
  $$\lfloor \gamma n \rfloor - 1 \le I_1(n) \le \lfloor \gamma n \rfloor + 3$$

E. Complejidad de Factores y Exponente Crítico

• Complejidad de Factores: Demuestran que $B$ es una palabra de Rote, lo que significa que su complejidad de factores (número de subpalabras distintas de longitud $n$) es exactamente $2n$para todo$n \ge 1$.
• Exponente Crítico: Determinan el exponente crítico de $B$ (la máxima potencia racional que puede aparecer en la secuencia):
  $$ce(B) = 2 + \frac{1}{\psi - 1} \approx 3.19148788$$
  Este valor es idéntico al exponente crítico de la palabra Tribonacci. La demostración se basa en el análisis de las longitudes de los factores bispeciales y sus palabras de retorno más cortas.

4. Significado e Impacto

• Validación de Conjeturas: Resuelve problemas abiertos planteados por Kimberling, proporcionando pruebas rigurosas donde antes solo existían conjeturas empíricas.
• Metodología Híbrida: El artículo sirve como un "manual de instrucciones" (primer) sobre cómo atacar secuencias definidas por reglas de inflación complejas combinando teoría de autómatas (para la construcción de modelos) y demostración automática (para la verificación de propiedades lógicas).
• Conexión Estructural: Revela que, a pesar de las reglas de generación aparentemente complejas y no morfismas, la secuencia de Kimberling es esencialmente una transformación morfológica de la palabra Tribonacci, una de las estructuras más estudiadas en la teoría de palabras.
• Herramientas Computacionales: Demuestra la potencia de Walnut para probar propiedades de balance y complejidad en secuencias que serían intratables mediante métodos puramente manuales.

En resumen, el paper transforma una secuencia curiosamente definida en un objeto matemático bien entendido, vinculándolo a la teoría clásica de palabras estandarizadas (episturmianas) y demostrando sus propiedades fundamentales mediante métodos computacionales modernos.