On a perturbed Hofstadter $Q$-recursion

Este artículo demuestra que la variante perturbada por paridad $\widetilde{Q}$ de la secuencia de Hofstadter está bien definida para todo $n$, exhibe una autosimilitud exacta gobernada por números de Catalan y satisface una cota asintótica precisa, sugiriendo que puede servir como un proxy manejable para la secuencia original $Q$.

Lo esencial

Imagina que tienes una máquina muy especial, un tipo de "recursión anidada". Es como un juego de espejos donde, para calcular el siguiente número, la máquina tiene que mirar hacia atrás en su propia historia, pero la distancia a la que mira depende de lo que encontró en el pasado.

El famoso Secuencia Q de Hofstadter es un ejemplo de esto. Es tan caótica y desordenada que, después de décadas, los matemáticos ni siquiera saben si la máquina se va a atascar o si siempre podrá calcular el siguiente número. Es como intentar predecir el clima en un planeta donde el viento cambia de dirección basado en la temperatura que acaba de medir.

El "Truco" del Papel: La Perturbación de Mantovanelli

En este artículo, el autor Benoît Cloitre analiza una versión modificada de esa máquina, creada por Mantovanelli. Imagina que a la máquina original le añadimos un pequeño "tictac" o un pulso regular: cada vez que calcula un número, le suma o resta 1 dependiendo de si es un paso par o impar (como un latido de corazón: latido, no-latido, latido, no-latido).

¿Qué pasa? ¡El caos desaparece!
Mientras la máquina original (Q) es como un borracho caminando por una cuerda floja, la máquina nueva ($\tilde{Q}$) se convierte en un bailarín de ballet con una coreografía perfecta.

La Analogía de los "Arcos" y el "Espejo"

El descubrimiento clave del papel es que esta nueva secuencia tiene una estructura de autosimilitud. Imagina que dibujas la secuencia en un papel. Verás que se parece a una serie de arcos (como los de un puente o las olas del mar) que se repiten una y otra vez, pero en escalas más pequeñas dentro de las grandes.

1. Los Arcos: La secuencia sube y baja formando arcos. Algunos arcos son "positivos" (suben) y otros "negativos" (bajan).
2. El Espejo: Dentro de cada arco, hay una simetría perfecta. Si miras la mitad izquierda del arco y la reflejas en un espejo, obtienes la mitad derecha. Es como si la secuencia se estuviera contando a sí misma una historia que se lee igual de izquierda a derecha que de derecha a izquierda (pero con un giro).
3. Los Números de Catalan: La forma en que estos arcos se construyen y crecen sigue una regla matemática muy famosa llamada "Números de Catalan". Piensa en ellos como las reglas de cómo se pueden organizar bloques de Lego para que encajen perfectamente sin caerse. El autor demuestra que la "frecuencia" de estos arcos sigue exactamente estas reglas.

El Resultado Principal: El Ritmo Perfecto

El objetivo del autor era responder dos preguntas:

1. ¿La máquina siempre funciona? Sí. Demuestra que $\tilde{Q}$ está definida para siempre y nunca se rompe.
2. ¿Hacia dónde se dirige la secuencia? Hacia la mitad.

Si divides el número que da la máquina ($\tilde{Q}(n)$) por el número de pasos que llevas ($n$), verás que el resultado se acerca cada vez más a 0.5 (la mitad).

• La velocidad: No llega a la mitad instantáneamente. Se acerca lentamente, como un coche frenando. El autor calcula exactamente qué tan rápido frena: la diferencia con la mitad es proporcional a $1/\sqrt{\log n}$. Es una forma elegante de decir que se estabiliza, pero con un ritmo muy específico.

¿Por qué es importante esto?

El autor sugiere algo fascinante: esta versión "perturbada" y ordenada ($\tilde{Q}$) podría ser la llave maestra para entender la versión original y caótica ($Q$).

Imagina que la secuencia original es un río desbordado e incontrolable. El autor ha encontrado un canal de riego perfecto ($\tilde{Q}$) que corre paralelo al río. Si pueden demostrar que la diferencia entre el río desbordado y el canal es pequeña (y sus experimentos numéricos sugieren que sí lo es), entonces podrían usar el canal para predecir el comportamiento del río.

En resumen:

• El Problema: Una secuencia matemática famosa es un caos impredecible.
• La Solución: Al añadir un pequeño "ritmo" (un tictac par/impar), el caos se transforma en una danza geométrica perfecta de arcos espejados.
• El Hallazgo: Esta danza sigue reglas precisas (Números de Catalan) y converge exactamente a la mitad.
• La Esperanza: Este modelo ordenado podría ayudarnos finalmente a resolver los misterios de la secuencia original y caótica.

Es como si, al estudiar cómo se mueve un péndulo perfecto en un laboratorio, pudiéramos finalmente entender cómo se mueve un árbol en medio de una tormenta.

Resumen técnico

Aquí presento un resumen técnico detallado del artículo "On a perturbed Hofstadter Q-recursion" de Benoît Cloitre, estructurado según los puntos solicitados.

1. El Problema: La Recurrencia de Hofstadter y su Perturbación

El artículo aborda uno de los problemas más famosos y resistentes en la teoría de números y las matemáticas discretas: la Secuencia Q de Hofstadter (OEIS A005185), definida por la recurrencia anidada:
$$Q(n) = Q(n - Q(n-1)) + Q(n - Q(n-2)), \quad Q(1)=Q(2)=1$$
A pesar de décadas de estudio, no se ha demostrado rigurosamente si $Q(n)$ está definida para todo $n$, ni si la relación $Q(n)/n$ converge. El comportamiento de la secuencia es caótico y sus fluctuaciones alrededor de $1/2$ son impredecibles.

En 2026, Mantovanelli introdujo una variante perturbada por paridad, denotada como $\tilde{Q}(n)$ (OEIS A394051), modificando la recurrencia original añadiendo un término $(-1)^n$:
$$\tilde{Q}(n) = \tilde{Q}(n - \tilde{Q}(n-1)) + \tilde{Q}(n - \tilde{Q}(n-2)) + (-1)^n, \quad \tilde{Q}(1)=\tilde{Q}(2)=1$$
El problema central de este trabajo es analizar rigurosamente el comportamiento asintótico de $\tilde{Q}(n)$. A diferencia de la secuencia original, esta versión perturbada exhibe una autosimilitud dyádica exacta, lo que sugiere que es un "proxy" tratable para entender la secuencia original caótica.

2. Metodología

El autor emplea una combinación de análisis combinatorio, teoría de autómatas y métodos analíticos de funciones generadoras. La metodología se divide en varias etapas clave:

• Descomposición en Arco (Arch Decomposition):
  Se define una secuencia auxiliar $R(n) = (\tilde{Q}(n)+1)/2$ y se separan los índices pares e impares en dos subsecuencias $A(m)$ y $B(m)$. La diferencia $\delta(m) = B(m) - A(m)$ oscila entre valores positivos y negativos, formando "arcos" alternos. La estructura de estos arcos es fundamental para el análisis.

• Máquina de Interleaving (Interleave Transducer):
  La recurrencia se reinterpreta como una máquina determinista de dos cintas binarias. La secuencia de pasos (diferencias $\Delta A$ y $\Delta B$) dentro de cada arco se codifica en "palabras de paso" ($P_r$ y $N_r$).
  Se demuestra que estas palabras se generan mediante un operador de interleaving (entrelazado) que toma palabras de niveles anteriores. Esto revela una estructura fractal y autosimilar.

• Propiedades Estructurales:
  Se prueba que las palabras de paso son anti-palindrómicas y balanceadas (igual número de ceros y unos). Esto permite modelar la altura de los arcos como caminos aleatorios (excursiones) con propiedades simétricas exactas.

• Dos Rutas de Análisis:

  • Ruta B (Frecuencias - Incondicional): Analiza la distribución de las visitas de las secuencias $A$ y $B$ a valores enteros en bloques dyádicos. Utiliza un método de "inversión monótona" y coeficientes binomiales centrales.
  • Ruta A (Amplitudes - Condicional): Analiza directamente la altura máxima de los arcos ($V^+(r)$). Utiliza una recursión de "escalera" (staircase recursion) y el método del kernel (relacionado con las funciones generadoras de Catalan) para derivar fórmulas exactas.

3. Contribuciones Clave

1. Bien-definición y Cotas: Se prueba que $\tilde{Q}(n)$ está definida para todo $n \ge 1$ y satisface $1 \le \tilde{Q}(n) \le n$, algo que no se sabe para la secuencia original $Q(n)$.
2. Estructura de Autosimilitud Exacta: Se establece que la secuencia perturbada posee una estructura fractal rigurosa gobernada por la interacción de dos cintas binarias, reemplazando el caos por un orden determinista.
3. Conexión con Números de Catalan: Se identifica que la dinámica de la secuencia está gobernada por el kernel algebraico $1 - z + xz^2 = 0$, cuya solución es la función generadora de los números de Catalan. Esto conecta la secuencia con estructuras combinatorias profundas (árboles meta-Fibonacci).
4. Prueba de Convergencia: Se demuestra que $\tilde{Q}(n)/n \to 1/2$.

4. Resultados Principales

El teorema principal (Teorema 1.1) establece dos resultados:

• Resultado Incondicional (Parte a):
  La tasa de convergencia es:
  $$\left| \frac{\tilde{Q}(n)}{n} - \frac{1}{2} \right| = O\left(\frac{1}{\sqrt{\log n}}\right)$$
  Esta cota se demuestra rigurosamente sin suposiciones adicionales, basándose en la ley de frecuencias de las visitas en los bloques dyádicos, donde el desequilibrio está controlado por coeficientes binomiales centrales $\binom{2k+2}{k+1}$.

• Resultado Condicional (Parte b):
  Bajo dos conjeturas computacionales verificadas hasta niveles bajos (Observaciones 9.4 y 9.10 sobre la "reclamación de récords" y la identificación de contadores de corridas), se obtiene una fórmula asintótica precisa para la envolvente de las fluctuaciones:
  $$\limsup_{n \to \infty} \left| \frac{\tilde{Q}(n)}{n} - \frac{1}{2} \right| \sqrt{\log_2 n} = \frac{1}{3\sqrt{2\pi}}$$
  Esto implica que la amplitud de los arcos crece como $V^+(r) \sim \frac{8}{3\sqrt{\pi}} \frac{4^r}{\sqrt{r}}$.

5. Significado e Implicaciones

• Proxy para Hofstadter: Los experimentos numéricos sugieren que la diferencia entre la secuencia original y la perturbada, $Q(n) - \tilde{Q}(n)$, es $O(n/\sqrt{\log n})$. Si esto se prueba, implicaría que la secuencia original $Q(n)$ también converge a $n/2$ y está bien definida para todo $n$, resolviendo un problema abierto de décadas.
• Nuevas Herramientas para Recurrencias Anidadas: El artículo introduce un marco metodológico (transductores de interleaving y descomposición en arcos) que podría aplicarse a otras secuencias meta-Fibonacci caóticas.
• Conexión Analítica: La aparición del kernel de Catalan y la tasa de convergencia $O(1/\sqrt{\log n})$ (similar a la secuencia de Conway-Mallows) sugiere una universalidad en el comportamiento de ciertas recurrencias anidadas perturbadas.
• Fenómeno de Golden Ratio: El autor nota que una perturbación similar en la secuencia de Conway-Mallows parece converger a $1/(2\phi)$ (donde $\phi$ es la razón áurea), indicando una interacción multiplicativa entre la profundidad de anidamiento y la perturbación de paridad.

En resumen, el artículo transforma un problema caótico en uno estructurado mediante una perturbación inteligente, demostrando que la adición de un término $(-1)^n$ regulariza la secuencia, permitiendo una descripción asintótica precisa y ofreciendo una vía prometedora para atacar la secuencia de Hofstadter original.