The Hofstadter consecutive-sum sequence omits infinitely many positive integers

Este artículo demuestra que la sucesión auto-generadora de Hofstadter definida por sumas consecutivas omite infinitos enteros positivos, resolviendo así una conjetura de la OEIS y estableciendo cotas asintóticas para su crecimiento.

Lo esencial

¡Hola! Vamos a desglosar este artículo matemático como si estuviéramos contando una historia alrededor de una fogata, sin usar fórmulas complicadas.

Imagina que tienes una máquina de hacer números muy especial. Esta máquina sigue unas reglas muy estrictas para crear una lista de números, uno tras otro. A esta lista la llamaremos "La Secuencia de Hofstadter".

1. ¿Cómo funciona la máquina? (La Regla del Juego)

La máquina empieza con dos números: 1 y 2.
A partir de ahí, para crear el siguiente número, la máquina tiene que buscar en su lista de números anteriores y encontrar una suma de números consecutivos (números que están pegados uno al lado del otro en la lista).

Pero hay una regla de oro: La máquina siempre elige el número más pequeño posible que cumpla esta condición y que sea más grande que el último número que puso.

• Ejemplo:
  • Ya tenemos: 1, 2.
  • ¿Qué sigue?
    • ¿Podemos sumar 1+2? Sí, da 3. Es el más pequeño posible. -> Lista: 1, 2, 3.
    • ¿Qué sigue?
    • ¿Podemos sumar 2+3? Sí, da 5. (Nota: 1+2+3=6, pero 5 es más pequeño). -> Lista: 1, 2, 3, 5.
    • ¿Qué sigue?
    • ¿Podemos sumar 3+5? Sí, da 8. (Ojo: 4 no se puede hacer porque no hay dos números consecutivos que sumen 4). -> Lista: 1, 2, 3, 5, 8.

La lista empieza a verse así: 1, 2, 3, 5, 6, 8, 10, 11, 14...

2. El Gran Misterio (¿Qué números se pierden?)

Si miras la lista, te darás cuenta de algo curioso: faltan números.
El número 4 no está. El 7 no está. El 9 tampoco. El 12 tampoco.

Durante mucho tiempo, los matemáticos se preguntaron: "¿Esta máquina se olvidará de algunos números solo al principio, o se olvidará de infinitos números para siempre?"

Algunos pensaban que, como la máquina es muy "avispada" y elige el número más pequeño, eventualmente llenaría todos los huecos y tendría casi todos los números enteros (como 1, 2, 3, 4, 5, 6...).

3. La Gran Revelación del Autor (Quanyu Tang)

El autor de este paper, Quanyu Tang, ha demostrado que la máquina nunca dejará de olvidar números.

La analogía de la escalera rota:
Imagina que estás subiendo una escalera infinita. La regla de la máquina es que cada peldaño debe ser la suma de dos peldaños anteriores que estén pegados.
Tang demuestra que, a medida que subes, la escalera empieza a tener huecos cada vez más grandes. No es que falten solo unos pocos peldaños al principio; la escalera se vuelve cada vez más "esquelética".

En lenguaje matemático simple:

• Si la lista tiene el número 1000, no significa que haya tenido 1000 números antes. Probablemente solo tuvo 990, y faltaron 10.
• Si la lista tiene el número 1.000.000, faltan miles de números.
• Conclusión: La diferencia entre el número que tienes y su posición en la lista crece infinitamente. La máquina olvida infinitos números positivos.

4. ¿Qué tan rápido crece? (El límite de velocidad)

Además de decir "sí, faltan infinitos", Tang también calculó qué tan rápido crece esta lista.

Imagina que la lista crece como un árbol.

• Si creciera linealmente (como un palo recto), sería muy lento.
• Si creciera exponencialmente (como un virus), sería muy rápido.

Tang demostró que esta lista crece más rápido que una línea recta, pero mucho más lento que una explosión. Es como un árbol que se estira, pero con ramas que se rompen (los números que faltan).

Ha encontrado una fórmula que actúa como un "techo" o límite superior para decirnos que el número no puede crecer demasiado rápido. Es una fórmula un poco rara (con exponentes extraños), pero lo importante es que es una fórmula matemática, lo que nos da una idea clara de la velocidad de crecimiento.

5. ¿Por qué es importante?

Este paper cierra un debate que duró décadas.

• Antes: "¿Se olvidará de infinitos números? ¡Quién sabe! Parece que no, pero no tenemos prueba".
• Ahora: "¡Sí! Y no solo eso, podemos decirte exactamente cómo se comporta su crecimiento".

El autor también menciona que, aunque tiene una fórmula para el "techo" (la velocidad máxima), cree que la realidad es más simple y que la lista crece casi como una línea recta, pero con esos "huecos" que se hacen cada vez más grandes.

Resumen en una frase

La máquina de Hofstadter es como un constructor de puentes que, al intentar usar solo piezas que encajan perfectamente con las anteriores, termina dejando huecos cada vez más grandes en su camino, olvidando infinitos números en el proceso, y el autor ha demostrado matemáticamente que esto es inevitable y ha calculado qué tan rápido se aleja de la línea recta perfecta.

¡Es un trabajo brillante que combina la lógica de los juegos de números con herramientas matemáticas muy avanzadas para resolver un acertijo antiguo!

Resumen técnico

Resumen Técnico: La Secuencia de Suma Consecutiva de Hofstadter Omite Infinitos Enteros Positivos

1. El Problema

El artículo aborda el comportamiento asintótico de una secuencia auto-generadora definida por un proceso "codicioso" (greedy), conocida como la Secuencia de Hofstadter (registro OEIS A005243).

• Definición: La secuencia $(a_n)_{n \ge 1}$ comienza con $a_1 = 1, a_2 = 2$. Para $k \ge 3$, $a_k$ se define como el menor entero mayor que $a_{k-1}$ que puede expresarse como la suma de al menos dos términos consecutivos anteriores de la secuencia:
  $$a_k = \sum_{i=p}^{q} a_i \quad \text{para algunos } 1 \le p \le q \le k-1, \text{ con } q-p \ge 1.$$
• La Conjetura: Aunque numéricamente la secuencia parece contener "la mayoría" de los enteros, omite ciertos valores (4, 7, 9, 12, etc.). La Conjetura 1.2 (OEIS A005243) postula que la secuencia omite infinitos enteros positivos.
• Objetivo: Determinar el comportamiento asintótico de $a_n$ y probar si la secuencia omite infinitos números.

2. Metodología y Herramientas

El autor emplea una combinación de teoría de números, combinatoria aditiva y análisis de estructuras recursivas. La metodología se divide en dos partes principales: una demostración cualitativa (para la omisión infinita) y una cota superior cuantitativa.

A. Generalización y Estructura Monótona

• Se define una clase más amplia de secuencias $(a^u_n)$ generadas a partir de una "semilla" arbitraria $u$ de longitud $s \ge 2$.
• Se introduce el término de exceso $b_n = a_n - n$.
• Lema de Monotonía: Se demuestra que la secuencia de excesos $(b_n)$ es no decreciente para $n \ge s$.
• Estrategia de Contradicción: Se asume que $(b_n)$ está acotada. Esto implicaría que, eventualmente, la secuencia se vuelve lineal ($a_n = n + B$).

B. Análisis de la Cola Lineal y Ecuaciones Diofánticas

• Si la secuencia fuera lineal ($a_n = n+B$), los términos grandes serían potencias de 2 (debido a la estructura de sumas consecutivas).
• El autor analiza cómo las potencias de 2 se descomponen en sumas de términos consecutivos bajo la hipótesis lineal.
• Esto conduce a una ecuación de la forma:
  $$2^r = C + \frac{v(v+1)}{2} - \frac{(T-1)T}{2} \implies v^2 + v + E_C = 2^{r+1}$$
  donde $E_C$ pertenece a un conjunto finito de constantes.
• Teorema de Schinzel-Tijdeman: Se aplica un resultado profundo que establece que la ecuación $y^k = P(x)$ (donde $P$ es un polinomio con al menos dos ceros simples) tiene un número finito de soluciones enteras para $k > 2$.
• Dado que la ecuación derivada tendría infinitas soluciones si la secuencia fuera lineal, se llega a una contradicción. Por tanto, $b_n$ no puede estar acotada.

C. Cota Superior Cuantitativa (Combinatoria Aditiva)

• Para la secuencia clásica, se busca una cota superior polinómica.
• Se observa que el conjunto de sumas consecutivas $R_m$ es un subconjunto de la diferencia de un conjunto convexo de sumas parciales.
• Conjuntos Convexos: El conjunto de sumas parciales $\{s_0, \dots, s_m\}$ es convexo (las diferencias consecutivas son estrictamente crecientes).
• Teorema de Bloom: Se utiliza una cota inferior reciente para el tamaño del conjunto de diferencias de conjuntos convexos finitos: $|A - A| \gg |A|^{6681/4175 - \eta}$.
• Recursión: Se establece una relación recursiva entre el índice $n$ y el valor $a_n$ basada en el crecimiento de la cantidad de enteros representables.
  $$a_n \le C_1 n^\alpha a_{\lceil C_1 n^\alpha \rceil}$$
  donde $\alpha = 1/\delta$ y $\delta \approx 6681/4175$.
• Iterando esta desigualdad, se obtiene una cota polinómica final.

3. Contribuciones Clave y Resultados Principales

Teorema 1.4 (Crecimiento Superlineal):
Para cualquier semilla finita de enteros positivos, la secuencia de excesos $(b_n = a_n - n)$ es no decreciente y no acotada.

• Corolario 1.5: Esto implica que $a_n = n + \omega(1)$. En consecuencia, el conjunto de valores de la secuencia omite infinitos enteros positivos. Esto resuelve afirmativamente la Conjetura 1.2.

Teorema 1.6 (Cota Superior Cuantitativa):
Para la secuencia clásica (semilla 1, 2), se establece una cota superior polinómica:
$$a_n \ll_\varepsilon n^{\frac{4175}{2506} + \varepsilon}$$
donde $\frac{4175}{2506} \approx 1.666$.

• Este es el primer límite polinómico conocido para este problema.

4. Significado y Discusión

• Resolución de un Problema Abierto: El trabajo confirma definitivamente que la secuencia de Hofstadter no es una permutación de los enteros positivos, sino que deja "huecos" infinitos, resolviendo una pregunta abierta de décadas en la OEIS y en problemas de Erdős.
• Conexión Interdisciplinaria: El artículo conecta la teoría de secuencias auto-generadoras con resultados profundos de la teoría de números (Schinzel-Tijdeman) y la combinatoria aditiva (límites de conjuntos convexos de Bloom).
• Brecha Asintótica:
  • La cota inferior es $a_n \ge n + \omega(1)$ (crecimiento ligeramente superior a lineal).
  • La cota superior es $a_n \ll n^{1.666}$.
  • Existe una brecha significativa entre ambas. El autor sugiere que el crecimiento real es mucho más cercano a lo lineal.
• Evidencia Numérica: El autor presenta datos computacionales ($n \le 30,000$) que sugieren que el exceso $b_n$ crece como una potencia de $n$ con un exponente $\alpha$ tal que $1/5 < \alpha < 1/2$, posiblemente cerca de$1/3$.
• Generalización: Los resultados cualitativos se aplican a cualquier semilla finita, no solo a $(1, 2)$.

Conclusión

Quanyu Tang demuestra que la secuencia de Hofstadter omite infinitos enteros, estableciendo que su crecimiento es estrictamente superior a $n$. Además, proporciona la primera cota superior polinómica, aunque el exponente obtenido ($\approx 1.666$) probablemente no sea óptimo, dejando abierta la cuestión de determinar el exponente exacto del crecimiento asintótico.