The Hofstadter consecutive-sum sequence omits infinitely many positive integers

Each language version is independently generated for its own context, not a direct translation.

🌟 Le Mystère de la Suite de Hofstadter : Pourquoi certains nombres disparaissent-ils ?

Imaginez que vous jouez à un jeu de construction avec des nombres, un peu comme si vous construisiez une tour brique par brique. C'est exactement ce que fait l'auteur de ce papier, Quanyu Tang, en étudiant une suite de nombres très particulière inventée par le célèbre mathématicien Douglas Hofstadter.

1. Le Jeu de la "Tour Croissante" 🏗️

Pour comprendre le problème, imaginons une règle très simple pour construire notre tour :

Le début : On pose deux briques : 1 et 2.
La règle magique : Pour trouver la prochaine brique, on doit chercher le plus petit nombre possible qui est plus grand que la dernière brique posée, ET qui peut être obtenu en additionnant au moins deux briques consécutives déjà posées.

Exemple concret :

On a : 1, 2.
Peut-on faire 3 ? Oui, $1 + 2 = 3$. On pose 3.
Peut-on faire 4 ?
- $2 + 3 = 5$ (trop grand).
- $1 + 2 + 3 = 6$ (trop grand).
- On ne peut pas faire 4 avec des briques consécutives (1+2=3, 2+3=5). Donc, 4 est sauté.
On pose 5 ($2+3$).
On pose 6 ($1+2+3$).
On pose 8 ($3+5$)... et ainsi de suite.

La suite obtenue ressemble à ceci : 1, 2, 3, 5, 6, 8, 10, 11...
Vous avez remarqué ? Les nombres 4, 7, 9, 12... n'apparaissent jamais. Ils sont "oubliés" par la machine.

2. La Grande Question 🤔

Depuis des années, les mathématiciens se demandent : "Est-ce que cette machine oublie une infinité de nombres, ou finit-elle par tout retrouver ?"

C'est comme si vous regardiez un aspirateur qui aspire des miettes sur un tapis. Au début, il laisse beaucoup de miettes derrière lui. Est-ce qu'il finira par tout nettoyer, ou va-t-il laisser des zones entières du tapis toujours sales pour toujours ?

Jusqu'à présent, personne ne le savait avec certitude. Certains pensaient que la suite finissait par devenir "dense" et remplir tous les trous.

3. La Découverte de Tang : "Non, il reste des trous !" 🕳️

Dans ce papier, Quanyu Tang prouve enfin la réponse : La suite oublie une infinité de nombres.

L'analogie de l'escalier :
Imaginez que vous montez un escalier. Normalement, vous montez une marche à la fois (1, 2, 3, 4...).
Mais ici, votre pied glisse parfois. Au lieu de monter d'une marche, vous devez sauter deux ou trois marches d'un coup pour atterrir sur une marche qui est la somme de deux marches précédentes.
Tang a prouvé que, plus vous montez haut, plus vous sautez de marches. Vous ne rattraperez jamais les marches manquantes. Il y a une infinité de marches qui restent vides.

En langage mathématique, il montre que la différence entre le nombre de la suite et son rang (par exemple, le 1000ème nombre moins 1000) devient de plus en plus grande. Plus on avance, plus la suite "s'éloigne" de la suite des nombres naturels classiques.

4. La Vitesse de la fuite 🚀

Le papier ne se contente pas de dire "il y a des trous". Il essaie aussi de mesurer à quelle vitesse la suite s'éloigne.

Tang utilise des outils mathématiques très pointus (liés à la géométrie des nombres et à la façon dont les formes convexes se comportent) pour dire :

La suite grandit, mais pas trop vite. Elle reste "polynomiale" (comme $n$ élevé à une certaine puissance).
Il donne une formule précise pour borner cette vitesse. C'est un peu comme dire : "Même si la suite saute, elle ne peut pas dépasser telle vitesse maximale."

C'est une première étape importante. Avant, on ne savait même pas si la suite restait proche des nombres normaux ou si elle explosait vers l'infini très vite. Maintenant, on sait qu'elle reste dans une certaine "zone de contrôle", mais qu'elle laisse définitivement des nombres derrière elle.

5. Pourquoi est-ce important ? 🧠

Ce résultat est une victoire pour la logique pure.

Pour les curieux : Cela répond à une question posée par Hofstadter il y a longtemps.
Pour les mathématiciens : Cela montre que même avec des règles très simples (additionner des voisins), le comportement peut devenir très complexe et laisser des "trous" infinis. C'est une leçon sur la façon dont l'ordre simple peut créer du désordre (ou des absences) imprévisibles.

En résumé 🎁

Imaginez une machine qui essaie de remplir une étagère avec des livres numérotés de 1 à l'infini.

La règle est stricte : elle ne peut mettre un livre que s'il est la somme de deux livres voisins déjà sur l'étagère.
L'ancien doute : "Peut-être qu'avec le temps, elle finira par mettre tous les livres, même ceux qui semblaient impossibles au début ?"
La réponse de Tang : NON. La machine est condamnée à laisser des espaces vides pour toujours. Plus l'étagère est grande, plus il y a de livres manquants.

C'est une preuve élégante que dans le monde des nombres, même avec des règles simples, il existe des zones d'ombre qui ne disparaîtront jamais.

Each language version is independently generated for its own context, not a direct translation.

Voici un résumé technique détaillé de l'article « The Hofstadter Consecutive-Sum Sequence Omits Infinitely Many Positive Integers » de Quanyu Tang, rédigé en français.

1. Problématique et Contexte

L'article s'intéresse à la séquence auto-génératrice de Hofstadter, notée $(a_n)_{n \ge 1}$ , définie par la suite A005243 dans l'OEIS (Online Encyclopedia of Integer Sequences).

Définition : La séquence commence par $a_1 = 1$ et $a_2 = 2$ . Pour $k \ge 3$ , $a_k$ est le plus petit entier strictement supérieur à $a_{k-1}$ qui peut s'écrire comme la somme d'au moins deux termes consécutifs précédents de la séquence.
$a_k = \sum_{i=p}^q a_i \quad \text{avec } 1 \le p \le q \le k-1 \text{ et } q-p \ge 1.$
Conjecture : Bien que la séquence semble contenir la plupart des entiers, elle omet visiblement certains nombres (4, 7, 9, 12, etc.). Une conjecture énoncée dans l'OEIS (Conjecture 1.2) postule que la séquence omet une infinité d'entiers positifs.
Objectif : Le papier vise à prouver cette conjecture et à établir des bornes asymptotiques sur la croissance de $a_n$ .

2. Méthodologie

L'auteur adopte une approche combinant l'analyse des structures arithmétiques, la théorie des nombres diophantiens et la combinatoire additive.

A. Généralisation et Analyse Qualitative (Sections 2 et 3)

L'auteur généralise d'abord le problème à une classe plus large de séquences définies par une « graine » initiale arbitraire $u = (u_1, \dots, u_s)$ .

Définition de l'excès : Il introduit la suite $b_n = a_n - n$ , qui mesure l'écart entre le terme et son indice.
Monotonie : Il démontre que $(b_n)$ est non décroissante pour $n$ suffisamment grand.
Argument par l'absurde : Pour prouver que $b_n \to \infty$ (et donc que des entiers sont omis), il suppose par l'absurde que $(b_n)$ est bornée. Cela impliquerait que la séquence devient linéaire ( $a_n = n + B$ ) pour $n$ grand.
Réduction Diophantienne : En utilisant la propriété que les puissances de 2 ne peuvent pas être écrites comme sommes de deux entiers consécutifs (Lemme 2.1), l'auteur montre que si la séquence était linéaire, les puissances de 2 apparaissant dans la séquence devraient satisfaire une équation de la forme :
$2^r = v^2 + v + E$
où $E$ appartient à un ensemble fini de constantes.
Utilisation du théorème de Schinzel-Tijdeman : Il applique un corollaire du théorème de Schinzel et Tijdeman (Lemme 2.2), qui stipule que l'équation $y^k = P(x)$ n'a qu'un nombre fini de solutions entières si $P$ a au moins deux zéros simples et $k > 2$ . Cela contredit l'hypothèse d'une infinité de solutions pour les puissances de 2, prouvant ainsi que $b_n$ n'est pas bornée.

B. Bornes Quantitatives Supérieures (Section 4)

Pour la séquence classique ( $u=(1,2)$ ), l'auteur établit une borne supérieure polynomiale.

Lien avec les sommes de prefix : Il définit les sommes partielles $s_m = \sum_{i=1}^m a_i$ . L'ensemble des sommes de termes consécutifs correspond aux différences de l'ensemble des sommes partielles $S_m = \{s_0, \dots, s_m\}$ .
Convexité : Il observe que l'ensemble $S_m$ est convexe au sens de la combinatoire additive (les différences consécutives sont strictement croissantes).
Théorème de Bloom : Il utilise un résultat récent de Bloom (2023) sur la taille des ensembles de différences pour les ensembles convexes finis : $|A - A| \gg |A|^{6681/4175 - \eta}$ .
Récurrence : En combinant la croissance du nombre d'entiers représentables (via le théorème de Bloom) avec la définition « gourmande » (greedy) de la séquence, il établit une récurrence sur $a_n$ .
Itération : Par itération de cette récurrence, il obtient une borne supérieure polynomiale.

3. Résultats Principaux

Résultat Qualitatif (Théorème 1.4 et Corollaire 1.5)

Pour toute graine initiale finie d'entiers positifs, la suite $b_n = a_n - n$ est non décroissante et non bornée.
Conséquence : $a_n = n + \omega(1)$ . Cela signifie que $a_n - n$ tend vers l'infini.
Conclusion majeure : La séquence omet une infinité d'entiers positifs. Cela confirme la Conjecture 1.2 de l'OEIS.

Résultat Quantitatif (Théorème 1.6)

Pour la séquence classique de Hofstadter, l'auteur prouve une borne supérieure polynomiale. Pour tout $\varepsilon > 0$ , il existe une constante $C_\varepsilon$ telle que :
$a_n \le C_\varepsilon n^{4175/2506 + \varepsilon}$
(L'exposant est approximativement $1.666$).
C'est la première borne polynomiale connue pour ce problème.

4. Signification et Perspectives

Résolution d'un problème ouvert : L'article résout définitivement la question de l'omission infinie d'entiers posée par Hofstadter et enregistrée dans l'OEIS.
Avancée méthodologique : L'application des bornes d'ensembles de différences pour les ensembles convexes (théorème de Bloom) à un problème de séquences auto-génératrices est une innovation significative.
Gap asymptotique : Bien que la borne supérieure soit polynomiale ( $n^{1.66...}$ ), les données numériques suggèrent une croissance beaucoup plus proche du linéaire. L'auteur note que si la conjecture de Erdős-Hegyvári sur les ensembles convexes ( $|A-A| \gg |A|^{2-o(1)}$ ) était vraie, la méthode donnerait $a_n \le n^{1+o(1)}$ . Cependant, même avec cette hypothèse, la méthode actuelle ne parvient pas à prouver $a_n \ll n$ .
Comportement asymptotique : Les simulations numériques suggèrent que l'excès $b_n$ croît comme une puissance de $n$ ( $b_n \approx n^\alpha$ ) avec $1/5 < \alpha < 1/2 $, potentiellement proche de$ 1/3$.

En résumé, ce papier établit rigoureusement que la séquence de Hofstadter est « lacunaire » (elle saute une infinité de nombres) et fournit la première estimation quantitative de sa vitesse de croissance, reliant ainsi la théorie des nombres, la combinatoire additive et les séquences récursives.