The Golden Sieve

Cet article réexamine le crible d'or, un processus d'effacement autoréférentiel qui, appliqué aux nombres naturels ou aux progressions arithmétiques, établit des liens avec les suites à hoquets, les partitions complémentaires de Fraenkel et les paires de Wythoff, tout en introduisant un crible d'extraction dont l'action est régie par une transformation affine explicite.

L'essentiel

Voici une explication de l'article « Le Tamis d'Or » de Benoit Cloitre, traduite en langage simple et imagé pour le grand public.

🌟 Le Tamis d'Or : Une Danse Numérique

Imaginez une longue file de personnes, numérotées de 1 à l'infini, attendant patiemment. C'est notre point de départ : la suite des nombres naturels (1, 2, 3, 4...).

Maintenant, imaginons un jeu de rôle très étrange, un peu comme un jeu de « Élimination » dans un camp de vacances, mais où les règles sont dictées par les nombres eux-mêmes. C'est ce que l'auteur appelle le Tamis d'Or.

1. Le Mécanisme : Le Chef d'Orchestre et le Soliste

Le jeu se déroule étape par étape. À chaque tour $n$ :

1. Le Chef d'Orchestre (le pointeur) : Il regarde la personne qui se trouve à la position $n$ dans la file actuelle. Disons que c'est le numéro 5.
2. Le Soliste (la cible) : Le Chef d'Orchestre utilise ce numéro 5 comme une instruction. Il dit : « Va chercher la personne qui se trouve à la position 5 dans la file ! »
3. L'Élimination : La personne trouvée à la position 5 est retirée de la file (elle est « éliminée »).
4. Le Survivant : La personne qui était à la position $n$ (le Chef d'Orchestre) reste en vie.

On répète ce processus à l'infini. À la fin, on obtient deux groupes distincts :

• Les Éliminés (ceux qui ont été retirés).
• Les Survivants (ceux qui sont restés).

2. La Magie du Nombre d'Or (Le Cas Classique)

Si on commence avec la file normale (1, 2, 3...), quelque chose de magnifique se produit. Les survivants et les éliminés ne sont pas mélangés au hasard. Ils suivent une règle très stricte liée au Nombre d'Or ($\phi \approx 1,618$), ce nombre célèbre qui apparaît dans les coquillages, les tournesols et l'art.

• Les survivants forment une suite connue sous le nom de Suite de Wythoff.
• Les écarts entre deux survivants successifs ne sont jamais au hasard : ils valent soit 1, soit 2.
• La décision de faire un écart de 1 ou de 2 dépend d'une règle bizarre : « Si le numéro de l'étape actuelle existe déjà dans la liste des survivants, on saute de 2. Sinon, on saute de 1. »

C'est comme si la file se regardait dans un miroir pour décider de son propre avenir. L'auteur appelle cela une séquence « Hoquet » (hiccup), car la suite « hoquette » entre deux vitesses différentes selon une règle interne.

3. Et si on changeait la file de départ ?

L'article explore ce qui se passe si on ne commence pas avec 1, 2, 3..., mais avec une file qui saute déjà, par exemple : 2, 4, 6, 8... (les nombres pairs) ou 3, 6, 9... (les multiples de 3).

L'auteur découvre que la magie opère toujours !

• Même si on change le point de départ, les survivants et les éliminés s'organisent toujours en deux groupes qui se complètent parfaitement (comme deux pièces de puzzle qui remplissent tout l'espace sans se chevaucher).
• La règle du « hoquet » reste la même, mais les nombres changent. C'est comme si on avait appliqué une transformation géométrique sur le jeu.
• L'auteur montre que ce jeu est lié à des équations mathématiques très anciennes (les équations de Fraenkel) utilisées dans des jeux de stratégie.

4. Le « Tamis d'Argent » (L'Extraction)

L'auteur introduit aussi un cousin du Tamis d'Or, qu'il appelle le Tamis d'Argent.

• Dans le Tamis d'Or, on regarde une position précise pour décider qui éliminer.
• Dans le Tamis d'Argent, on est plus direct : on prend toujours le premier de la file (le plus petit nombre) pour le sauver, puis on en élimine quelques-uns juste après selon une règle similaire.
• Ce tamis permet de générer d'autres suites célèbres, comme celle étudiée par des chercheurs nommés Bosma, Dekking et Steiner.

5. Pourquoi est-ce important ?

Au-delà du jeu, cet article montre que des règles très simples (lire un nombre, sauter à une position, effacer) peuvent créer des structures mathématiques extrêmement rigides et prévisibles.

• Le lien avec la nature : Ces suites ressemblent à la façon dont les feuilles poussent sur une tige ou comment les pétales s'organisent dans une fleur (phénomènes liés au Nombre d'Or).
• Les jeux : Ces suites décrivent les positions gagnantes dans certains jeux de stratégie complexes.
• L'informatique : Comprendre ces règles aide à créer des algorithmes plus efficaces et à coder des séquences complexes.

En résumé

Benoit Cloitre nous invite à jouer à un jeu d'élimination où les nombres se jugent eux-mêmes. Il nous montre que même avec des règles simples, l'univers des nombres produit des motifs d'une beauté et d'une régularité surprenantes, liés au Nombre d'Or et à des structures mathématiques profondes. C'est une démonstration que la complexité peut naître de la simplicité, un peu comme une mélodie magnifique peut naître de quelques notes répétées.

Résumé technique

Voici un résumé technique détaillé de l'article « The Golden Sieve » de Benoit Cloitre, rédigé en français.

Titre : Le Crible d'Or (The Golden Sieve)

Auteur : Benoit Cloitre (Paris, France)
Date : Mars 2026
Sujet : Théorie des nombres, Séquences auto-référentielles, Combinatoire des mots, Jeux combinatoires.

---

1. Problématique et Contexte

L'article revisite un processus de suppression déterministe sur les séquences d'entiers positifs croissants, appelé le crible d'or (introduit par l'auteur en 2002 sous la référence OEIS A099267).

Le problème central est d'analyser le comportement de ce crible lorsqu'il est appliqué non seulement aux entiers naturels $\mathbb{N}$, mais aussi aux progressions arithmétiques de la forme $W_0 = a\mathbb{N} + b$. L'objectif est de comprendre comment ce processus simple génère des structures rigides, des partitions complémentaires et des séquences auto-référentielles, en particulier en lien avec les séquences de Beatty, les partitions de Fraenkel et les « séquences hiccup » (étudiées récemment par Fokkink et Joshi).

2. Méthodologie

Le papier repose sur une analyse combinatoire et dynamique rigoureuse, structurée autour de plusieurs axes méthodologiques :

• Définition du processus de crible : À chaque étape $n$, on lit la $n$-ième entrée $h_n$ de la séquence courante $W_{n-1}$. Cette valeur sert d'index de position pour supprimer l'élément situé à cette position ($d_n = W_{n-1}(h_n)$). La séquence résultante est partitionnée en survivants $(s_n)$ et supprimés $(d_n)$.
• Normalisation et Réduction : Pour les progressions arithmétiques $W_0 = a\mathbb{N} + b$, l'auteur introduit une application de normalisation qui ramène le problème à une étude sur $\mathbb{N}$, mais avec des paramètres modifiés. Cela permet de distinguer le cas dégénéré ($a=1, b=0$) des cas non dégénérés ($a \ge 2$).
• Identités de Rang et Équations Complémentaires : L'analyse utilise des identités de rang affine reliant les survivants et les éléments supprimés, les connectant aux équations complémentaires de Fraenkel et aux transformations de rang de Kimberling.
• Séquences Hiccup : L'article formalise la connexion avec les séquences hiccup $(j, x, y, z)$, où le saut (gap) entre termes consécutifs dépend de la présence d'un indice dans l'ensemble des valeurs de la séquence elle-même.
• Introduction du « Crible d'Extraction » : Une nouvelle famille de cribles est introduite pour montrer qu'elle génère directement les séquences hiccup, offrant un point de vue dynamique alternatif au crible d'or.
• Analyse Asymptotique et Théorie des Nombres : Utilisation de l'analyse de la pente asymptotique, des fractions continues et de la théorie des mots (mots de Sturmian, complexité factorielle) pour caractériser les séquences générées.

3. Résultats Clés et Contributions

A. Le cas fondamental : $W_0 = \mathbb{N}$

• Identification de Wythoff : Le crible appliqué aux entiers naturels produit une partition qui, à un décalage près, correspond à la paire de Wythoff $(\lfloor n\phi \rfloor, \lfloor n\phi^2 \rfloor)$, où $\phi$ est le nombre d'or.
• Règle Hiccup : Les séquences de survivants et de supprimés suivent des règles de saut auto-référentielles. Par exemple, la séquence des supprimés $(d_n)$ est une séquence hiccup $(0, 1, 2, 3)$, où le saut est 2 si $n$ appartient à l'ensemble des supprimés, et 3 sinon.
• Mot de Gap : Le mot binaire des écarts correspond au mot de Fibonacci (mot de Sturmian de pente $1/\phi$).

B. Généralisation aux Progressions Arithmétiques ($W_0 = a\mathbb{N} + b$)

• Identité Pointeur-Survivant : Pour $a \ge 2$, le pointeur $h_n$ à l'étape $n$ correspond toujours au $n$-ième survivant $s_n$. Cela stabilise le préfixe de la séquence de travail.
• Relation Affine (Identité de Rang) : Il existe une relation affine stricte entre les survivants normalisés $\sigma_n$ et les supprimés normalisés $\delta_n$ :
  $$\delta_n = a\sigma_n + n + (b-1)$$
  Cette équation place le crible dans le cadre des équations complémentaires de Fraenkel pour le jeu $NIM(a, 1)$.
• Propriété à Deux Sauts : Les écarts normalisés des survivants ne prennent que deux valeurs $\{1, 2\}$. Le choix du saut est gouverné par un mot binaire $H(n)$ qui dépend de la membership de $n$ dans l'ensemble des survivants.
• Pente Asymptotique : La pente limite $\alpha(a) = \lim \sigma_n/n$ est l'unique racine positive dans $(1, 2)$ de l'équation quadratique $a\alpha^2 - a\alpha - 1 = 0$. Contrairement au cas $a=1$, pour $a \ge 2$, les séquences ne sont pas des suites de Beatty.
• Nature Combinatoire du Mot de Gap : Pour $a \ge 2$, le mot binaire $H$ n'est généralement pas de Sturmian. L'article pose la question de savoir si ces mots sont morphiques, $k$-automatiques ou Ostrowski-automatiques.

C. Le Crible sur les Carrés Parfaits ($W_0 = \{n^2\}$)

• L'application du crible aux carrés parfaits introduit une récurrence auto-référentielle quadratique.
• La croissance des indices de racine carrée des survivants $\mu_n$ suit une expansion en tour de racines alternées :
  $$\mu_n = n + n^{1/2} - n^{1/4} + n^{1/8} - \dots + O(\log \log n)$$
• La règle de saut dépend de la présence de $n$ dans un « ensemble d'ombre » construit à partir des carrés des survivants.

D. Le Crible d'Extraction et les Séquences Hiccup

• L'auteur définit un crible d'extraction ($C_{j,y,z}$) où l'on extrait le minimum et supprime un nombre fixe d'éléments suivants selon un test de membership.
• Théorème de Transformation Affine : Ce crible réalise directement les séquences hiccup. L'application d'un crible d'extraction sur une progression $a\mathbb{N} + b$ transforme les paramètres de la séquence hiccup $(j, x, y, z)$ en $(j, a+b, ay, az)$.
• Cela permet de dériver des représentations de Beatty explicites pour certaines séquences hiccup (notamment la séquence de Bosma-Dekking-Steiner, OEIS A086377, générée par le « crible d'argent » $C_{1,3,2}$).

4. Signification et Implications

• Unification Théorique : Le papier unifie des constructions apparemment disparates (jeux de Wythoff, partitions de Fraenkel, séquences auto-référentielles de l'OEIS) sous un seul mécanisme dynamique : le crible d'or.
• Lien avec la Théorie des Jeux : Il établit un lien direct entre le processus de crible et les positions P (positions gagnantes pour le joueur précédent) des jeux $NIM(a, 1)$ généralisés.
• Nouveaux Outils Combinatoires : L'introduction du crible d'extraction fournit un mécanisme dynamique simple pour générer des séquences hiccup, offrant une alternative aux définitions récursives statiques.
• Questions Ouvertes : L'article soulève des problèmes profonds sur la nature combinatoire des mots de gap pour $a \ge 2$ (automatisme, complexité factorielle) et invite à l'utilisation d'outils comme Walnut pour prouver des propriétés d'automatisme.

En résumé, ce travail démontre la richesse structurelle d'un processus de suppression élémentaire, révélant qu'il engendre des partitions complémentaires rigides, des lois de croissance asymptotique précises et des structures de mots complexes, reliant ainsi la théorie des nombres, la combinatoire des mots et la théorie des jeux.