Almost Golomb Sequences

Aquí presento un resumen técnico detallado del artículo "Almost Golomb Sequences" (Secuencias casi Golomb) de Benoît Cloitre, estructurado según los puntos solicitados.

1. Planteamiento del Problema

El artículo aborda la generalización de la Secuencia de Golomb (OEIS A001462), una secuencia única de enteros positivos no decrecientes donde el entero $n$ aparece exactamente $a(n)$ veces. La secuencia de Golomb original satisface la regla autorreferencial global:
$$a\left( \sum_{k=1}^{n} a(k) \right) = n$$
Esta secuencia crece suavemente como una potencia de $n$ (asintóticamente $n^{\phi-1}$, donde $\phi$ es la razón áurea) y no es $k$-regular para ningún $k \ge 2$.

El problema central es investigar qué ocurre cuando se reemplaza la suma acumulada infinita (memoria total) por una ventana deslizante de tamaño fijo $r$. Esto define las Secuencias casi Golomb de orden $r$, denotadas como $(a(n))_{n \ge 1}$, que satisfacen:
$$a\left( a(n) + a(n-1) + \dots + a(n-r+1) \right) = n$$
con la condición de que $a(n)$ sea el entero mínimo posible $\ge a(n-1)$ que satisface la ecuación. La pregunta es cómo esta truncación de memoria infinita a memoria finita altera la naturaleza asintótica, la regularidad y la estructura combinatoria de la secuencia.

2. Metodología

El autor emplea una combinación de técnicas analíticas, constructivas y computacionales:

• Estructura de Ejecución (Run Structure): Se demuestra primero que la secuencia tiene una estructura de "bloques" o ejecuciones donde los valores aumentan en 0 o 1, y se identifican las posiciones exactas de inicio de cada nuevo valor.
• Criterio de Allouche-Shallit: Se utiliza para probar la $r$-regularidad (una generalización de la $r$-automaticidad para secuencias de valores enteros). El objetivo es mostrar que el núcleo $r$-ádico de la secuencia genera un módulo finitamente generado sobre $\mathbb{Z}$.
• Desanidación (Denesting): Se buscan fórmulas explícitas que expresen $a(rn+i)$ en términos de $a(n)$ y sus vecinos, más una secuencia correctora binaria. Esto convierte la definición recursiva implícita en una definición recursiva explícita basada en la representación en base $r$.
• Certificación Computacional (Walnut): Para los casos $r=4$ y $r=5$, donde las derivaciones manuales son complejas, se utiliza el demostrador de teoremas Walnut. Se identifican patrones de recurrencia y luego se certifican formalmente mediante autómatas finitos deterministas con salida (DFAO).
• Análisis Asintótico: Se estudian los límites de la razón $a(n)/n$ a lo largo de progresiones geométricas específicas para demostrar la no convergencia.

3. Contribuciones Clave

1. Prueba Universal de $r$-regularidad: Se demuestra (Teorema 2.9) que para todo $r \ge 2$, la secuencia casi Golomb es $r$-regular. Esto marca un cambio fundamental respecto a la secuencia de Golomb original (que no es $k$-regular).
2. Fórmulas de Desanidación Explícitas: Se obtienen fórmulas cerradas para los casos $r \in \{2, 3, 4, 5\}$. Estas fórmulas expresan $a(rn+i)$ como una combinación lineal de términos anteriores más una secuencia correctora binaria ($\epsilon(n)$) que es $r$-automática.
   • Para $r=2$: Se encuentra una recurrencia anidada tipo Mallows.
   • Para $r=3, 4, 5$: Se identifican secuencias correctoras complejas gobernadas por autómatas finitos.
3. No Convergencia de $a(n)/n$: Se prueba que, a diferencia de la secuencia de Golomb (que converge a una constante), la razón $a(n)/n$ en las secuencias casi Golomb no converge. Oscila entre dos (o más) puntos límite racionales distintos, dependiendo de la subsecuencia analizada.
4. Interpretaciones Combinatorias:
   • Para $r=2$: Se identifica una caracterización basada en el "segundo bit" de la representación binaria y una regla de autómata celular booleano.
   • Para $r=3$: Se descubre una regla de sustitución palindrómica.
5. Estructura Meta-Golomb Conjetural: Se propone una conjetura profunda (Sección 9) que vincula la multiplicidad máxima de valores en las secuencias casi Golomb con la propia secuencia de Golomb. Los datos numéricos sugieren que el umbral de orden $r$ necesario para alcanzar una multiplicidad $k$ sigue exactamente la ley de la secuencia de Golomb.

4. Resultados Principales

• Cambio de Régimen: La truncación de la memoria transforma la secuencia de un crecimiento suave sublineal (ley de potencia) a un crecimiento lineal con oscilaciones discretas.
• Regularidad:
  • $r=2$: $a(n)$ es 2-regular. La secuencia de multiplicidades $N_2(n)$ es 2-automática.
  • $r=3$: $a(n)$ es 3-regular. Se requieren secuencias correctoras para manejar las desviaciones de la fórmula lineal simple.
  • $r=4, 5$: Se confirman mediante Walnut que son 4-regular y 5-regular respectivamente, con sistemas de corrección binaria más complejos.
• Límites de Oscilación:
  • Para $r=2$, $a(n)/n$ oscila entre $3/4$ y $2/3$.
  • Para $r=3$, oscila entre $8/15$ y $5/8$.
  • Para $r=4$ y $r=5$, se identifican pares de límites racionales distintos (ej. $25/48$ y $10/21$ para $r=4$).
• Conjetura de Estructura Meta: Los datos numéricos hasta $r=700$ apoyan la identidad $j_{k+1} - j_k = G(k)$, donde $j_k$ es el menor orden $r$ tal que la multiplicidad máxima alcanza $k$, y $G(k)$ es la secuencia de Golomb. Esto sugiere que la secuencia de Golomb "reaparece" como la ley que controla la jerarquía de las secuencias truncadas.

5. Significado e Impacto

Este trabajo es significativo por varias razones:

1. Puente entre Análisis y Teoría de Números: Conecta el comportamiento asintótico suave de las secuencias autorreferenciales clásicas con la estructura discreta y automática de las secuencias definidas por ventanas finitas.
2. Nueva Clase de Secuencias Automáticas: Introduce una familia rica de secuencias $r$-regulares que surgen de reglas de "divide y vencerás" (divide-and-conquer) con correcciones automáticas, ampliando el conocimiento sobre secuencias definidas por recursiones anidadas.
3. Fenómeno de Auto-referencia Recursiva: La conjetura de que la secuencia de Golomb gobierna los umbrales de multiplicidad de sus propias variantes truncadas es un hallazgo sorprendente que sugiere una profunda estructura matemática subyacente aún no completamente comprendida.
4. Herramientas Computacionales: El uso exitoso de Walnut para certificar identidades complejas en secuencias definidas implícitamente demuestra el poder de la verificación asistida por computadora en la teoría de secuencias numéricas.

En resumen, Cloitre demuestra que al restringir la memoria de la secuencia de Golomb, se pierde la suavidad analítica pero se gana una estructura combinatoria rica, regular y predecible mediante autómatas, revelando al mismo tiempo que la secuencia original permanece como el "esqueleto" oculto de esta nueva familia de secuencias.