🔢 mathematics

Almost Golomb Sequences

Cet article introduit les suites presque de Golomb, définies par une règle autoréférentielle à mémoire finie qui remplace la croissance lisse de la suite de Golomb par une croissance linéaire oscillatoire et une régularité $r$ , révélant une structure combinatoire riche où la suite originale réapparaît paradoxalement comme loi gouvernant l'ensemble des multiplicités maximales de cette nouvelle famille.

Auteurs originaux : Benoit Cloitre

Publié 2026-04-06

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Benoit Cloitre

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

🌟 Le Secret des Séquences "Presque Golomb"

Imaginez que vous essayez de construire une tour de Lego, mais avec une règle très bizarre : le nombre de fois où vous utilisez une pièce de taille $n$ doit être exactement égal à la taille de la pièce elle-même.

C'est ce qu'on appelle la séquence de Golomb. C'est une suite de nombres fascinante, étudiée depuis des décennies. Elle est "lisse", prévisible dans sa croissance globale, mais elle cache une complexité mathématique profonde (liée au nombre d'or, ce fameux $\phi$ qui apparaît dans les coquillages et les tournesols).

Mais Benoît Cloitre, l'auteur de ce papier, s'est demandé : "Et si on changeait un peu les règles ?"

Au lieu de se souvenir de toute l'histoire de la construction (de la première brique jusqu'à la dernière), qu'arriverait-il si la règle ne se souvenait que des $r$ dernières briques posées ? C'est comme si votre mémoire était un "filet" qui glisse sur les dernières actions, oubliant le passé lointain.

C'est ce qu'il appelle les séquences "Presque Golomb".

🧠 L'Analogie du Miroir et de la Fenêtre

Pour comprendre la différence, utilisons deux métaphores :

Golomb (La Mémoire Infinie) : Imaginez un miroir magique qui reflète toute votre vie. Pour savoir combien de fois vous devez répéter un mot, le miroir regarde tout ce que vous avez dit depuis votre naissance. Le résultat est une croissance douce et régulière, comme une courbe qui s'étire lentement.
Presque Golomb (La Fenêtre Glissante) : Maintenant, imaginez que vous ne pouvez regarder à travers le miroir que par une petite fenêtre carrée qui ne montre que les 3 ou 4 derniers mots. Vous avez une "mémoire à court terme".
- Le résultat ? Au lieu d'une courbe douce, vous obtenez une vague. La suite de nombres monte et descend de manière rythmique, comme une marée. Elle ne se stabilise jamais parfaitement ; elle oscille.

🔍 Ce que le papier découvre

L'auteur a analysé ce qui se passe quand on change la taille de cette fenêtre (notée $r$ ). Voici les découvertes principales, expliquées simplement :

1. La Mémoire change la Nature du Monstre

Quand la fenêtre est petite (par exemple, on ne regarde que les 2 ou 3 derniers nombres), la suite devient très structurée. Elle obéit à des règles simples et répétitives, comme un motif de tapisserie qui se répète. En mathématiques, on dit qu'elle devient "r-régulière" (elle suit des schémas prévisibles basés sur les chiffres de son nombre).

Analogie : La séquence de Golomb originale est comme une forêt sauvage et complexe. Les séquences "Presque Golomb" sont comme un jardin japonais où chaque pierre est placée selon un motif précis et répétitif.

2. Le Mystère de la Non-Convergence

Dans la version originale, si vous divisez la taille de la brique par son numéro, vous obtenez toujours le même nombre à la fin (une constante).
Dans les versions "Presque", ce nombre ne se fixe jamais. Il oscille entre deux valeurs.

Image : C'est comme un pendule qui ne s'arrête jamais. Il balance entre deux positions. L'auteur a calculé exactement entre quelles positions il oscille pour chaque taille de fenêtre.

3. Le Retour du Fantôme (La Grande Surprise)

C'est le moment le plus magique du papier.
L'auteur a regardé : "Combien de fois un nombre apparaît-il dans ces nouvelles suites ?" (Par exemple, combien de fois le nombre 5 apparaît-il ?).
Il a découvert que le nombre maximal de répétitions, pour toutes les tailles de fenêtres possibles, est gouverné par la séquence de Golomb originale !

L'Analogie du Miroir : Imaginez que vous créez des clones de vous-même avec des mémoires différentes. Vous vous demandez : "Qui est le plus fort ?" Et soudain, vous réalisez que la force de tous ces clones est dictée par... votre propre histoire originale.
- Le papier montre que la séquence de Golomb (celle qu'on a "tronquée" pour créer les nouvelles) réapparaît comme la loi suprême qui contrôle la famille entière de ses propres créations. C'est un cercle vertueux et fascinant.

🛠️ Comment ils ont fait ?

Pour prouver tout cela, l'auteur a utilisé deux outils :

Le Raisonnement Mathématique Pur : Pour les petits cas (fenêtres de taille 2, 3, 4, 5), il a trouvé des formules exactes, comme des recettes de cuisine pour calculer n'importe quel nombre de la suite.
L'Ordinateur (Walnut) : Pour vérifier que ces règles fonctionnent pour des milliards de nombres, il a utilisé un logiciel spécialisé capable de prouver des propriétés complexes sur les suites de nombres. C'est comme avoir un détecteur de mensonges mathématique qui vérifie chaque brique de la tour.

🎯 En Résumé

Ce papier nous dit que si on prend une règle mathématique célèbre et qu'on lui donne une "mémoire courte", on ne perd pas la magie, on la transforme :

La croissance devient ondulatoire (elle oscille).
La structure devient automatique (comme un code informatique).
Et le plus surprenant : l'original revient hanter ses créations, dictant combien de fois les nombres peuvent se répéter.

C'est une belle démonstration de la façon dont les mathématiques peuvent transformer un problème simple (une fenêtre glissante) en une structure riche, oscillante et profondément liée à ses origines.

1. Problématique et Contexte

L'article s'intéresse à une généralisation de la séquence de Golomb (OEIS A001462), une suite d'entiers positifs non décroissante unique où l'entier $n$ apparaît exactement $a(n)$ fois. La séquence de Golomb est définie par la règle auto-référentielle globale :
$a\left(\sum_{k=1}^n a(k)\right) = n$
Cette suite présente une croissance asymptotique lisse de type puissance ( $a(n) \sim C n^{\phi-1}$ , où $\phi$ est le nombre d'or) et n'est pas $k$ -régulière pour aucun $k \ge 2$ .

L'auteur introduit les séquences presque de Golomb (Almost Golomb sequences), notées $a_r(n)$ , obtenues en remplaçant la somme cumulative infinie par une fenêtre glissante de taille fixe $r$ . La définition est la suivante :
$a\left(\sum_{j=0}^{r-1} a(n-j)\right) = n$
avec $a(k)=0$ pour $k \le 0$ , et $a(n)$ étant le plus petit entier $\ge a(n-1)$ satisfaisant cette équation.

Question centrale : Comment le passage d'une mémoire infinie (règle globale) à une mémoire finie (fenêtre glissante de taille $r$ ) modifie-t-il la nature de la suite ? L'article explore la régularité, la croissance, et la structure combinatoire de ces nouvelles suites.

2. Méthodologie

L'approche de l'article combine plusieurs outils mathématiques et informatiques :

Analyse asymptotique et structure des runs : L'auteur établit d'abord la structure globale des séquences, en particulier la position des premières occurrences de chaque entier et la longueur de leurs « runs » (séquences d'entiers consécutifs identiques).
Théorie des suites automatiques et régulières : Utilisation des critères d'Allouche et Shallit pour prouver que les suites sont $r$ -régulières. Cela implique d'exprimer les termes $a(rn+i)$ en fonction d'un nombre fini de termes antérieurs et de suites correctrices.
Dénestration (Denesting) : Pour les cas $r \in \{2, 3, 4, 5\}$ , l'auteur dérive des formules explicites de type « diviser pour régner » (divide-and-conquer) en base $r$ . Ces formules relient $a(rn+i)$ à des combinaisons linéaires de $a(n+j)$ et de suites correctrices binaires.
Preuve assistée par ordinateur (Walnut) : Pour les cas $r=4$ et $r=5$ , les identités récursives complexes sont identifiées mathématiquement puis certifiées formellement à l'aide du prouveur de théorèmes Walnut, qui vérifie les propriétés des suites automatiques via des automates finis déterministes (DFAO).
Analyse numérique et conjectures : Une analyse extensive des multiplicités maximales pour différentes valeurs de $r$ mène à des conjectures reliant ces séquences à la séquence de Golomb originale.

3. Contributions et Résultats Clés

A. Régularité Universelle

Le résultat fondamental (Théorème 2.9) est que pour tout $r \ge 2$ , la suite presque de Golomb $a_r(n)$ est $r$ -régulière. Contrairement à la séquence de Golomb originale qui n'est régulière pour aucun $k$ , le passage à une fenêtre finie ramène la suite dans le cadre des suites automatiques/régulières. La preuve repose sur la réduction de la suite des différences $d(n) = a(n+1) - a(n)$ à une fenêtre locale finie.

B. Formules de Dénestration Explicites

L'article fournit des formules récursives précises pour les petits ordres :

Cas $r=2$ (Dyadique) : La suite satisfait des relations simples :
$a(2n) = a(n) + a(n+1) - 1$ et $a(2n+1) = a(n) + a(n+1)$ .
Elle admet aussi une récurrence imbriquée de type Mallows.
Cas $r=3$ (Ternaire) : La structure est plus complexe et fait intervenir une suite correctrice binaire $\varepsilon(n)$ (automatique en base 3) qui gère les écarts par rapport à la somme linéaire simple.
Cas $r=4$ et $r=5$ : Des systèmes de quatre et deux suites correctrices respectivement sont identifiés et certifiés par Walnut. Ces suites binaires contrôlent les termes « non génériques » de la récurrence.

C. Comportement Asymptotique et Non-Convergence

Un résultat surprenant est que le rapport $a(n)/n$ ne converge pas pour aucun $r \ge 2$ .

Alors que la séquence de Golomb converge vers une constante ( $\phi^{2-\phi}$ ), les séquences presque de Golomb oscillent entre deux (ou plus) points limites rationnels distincts.
Pour $r=2$ , les limites sont $3/4$ et $2/3$ .
Pour $r=3$ , les limites sont $8/15$ et $5/8$ .
Pour $r=4$ et $r=5$ , des limites similaires sont calculées.
Cela indique une croissance linéaire $a(n) \asymp n$ avec un facteur prépondérant oscillant, contrairement à la croissance sous-linéaire de Golomb.

D. Interprétations Combinatoires

Pour $r=2$ : La multiplicité des valeurs est caractérisée par le deuxième bit significatif de l'indice. La suite des différences $d(n)$ est générée par un automate cellulaire booléen simple.
Pour $r=3$ : La structure des blocs de différences admet une décomposition palindromique, révélant un mécanisme de rétroaction retardée qui explique les oscillations.

E. Structure Méta-Golomb (Conjecture)

L'auteur observe un phénomène numérique fascinant : la multiplicité maximale $M(r) = \sup_n N_r(n)$ (le nombre maximal de fois qu'un entier apparaît dans la suite d'ordre $r$ ) semble être gouvernée par la séquence de Golomb elle-même.

Soit $j_k$ le plus petit $r$ tel que $M(r) \ge k$ .
Les données numériques suggèrent que les différences $j_{k+1} - j_k$ coïncident exactement avec les termes de la séquence de Golomb $G(k)$ pour $k \ge 4$ .
Cela est formalisé dans la Conjecture 9.1 (Structure Méta-Golomb), qui réduit ce phénomène à deux conjectures de frontière : la « Prefix Conjecture » ( $a_r(r) = G(r-1)$ ) et la « Domination Lemma ». Si vraies, cela signifierait que la séquence de Golomb réapparaît comme la loi contrôlant la hiérarchie des séquences qu'elle a générées par troncature.

4. Signification et Impact

Cet article est significatif pour plusieurs raisons :

Changement de Paradigme : Il démontre comment une modification locale (fenêtre glissante) d'une règle auto-référentielle globale transforme radicalement la nature d'une suite : d'une croissance analytique irrationnelle et non-régulière à une croissance linéaire oscillatoire et $r$ -régulière.
Outils Méthodologiques : Il illustre la puissance de la combinaison entre l'analyse mathématique traditionnelle (dénestration, induction forte) et la vérification formelle assistée par ordinateur (Walnut) pour traiter des structures récursives complexes.
Connexions Profondes : La découverte d'un lien numérique entre les multiplicités maximales des séquences tronquées et la séquence de Golomb originale ouvre une nouvelle voie de recherche sur les structures auto-similaires et les hiérarchies de suites auto-référentielles.
Problèmes Ouverts : L'article laisse plusieurs questions ouvertes, notamment le comportement des moyennes de Cesàro pour $r \ge 3$ , la structure explicite pour $r \ge 6$ , et la transition de phase lorsque $r \to \infty$ (retour à la séquence de Golomb).

En résumé, Benoît Cloitre établit une théorie complète des séquences presque de Golomb, prouvant leur régularité, décrivant leur structure combinatoire fine, et révélant un lien inattendu avec la séquence de Golomb originale, enrichissant ainsi la théorie des suites d'entiers auto-référentielles.