Positive Lower Density for Hofstadter's $ab-1$ Problem

Le Jeu Infini de la Construction de Nombres

Imaginez un terrain de jeu vaste et sans fin où les nombres sont les jouets. Dans le monde des mathématiques, plus précisément dans une branche appelée la théorie des nombres, les chercheurs adorent jouer à des jeux avec des règles qui génèrent de nouveaux nombres à partir d'anciens. L'un des types de jeux les plus célèbres implique la « récurrence » ou le « renouvellement ». Pensez à un jeu de chaises musicales, mais au lieu de personnes, ce sont des nombres, et au lieu d'une chaise, c'est une place spécifique sur une droite numérique. La grande question que les mathématiciens posent depuis des décennies est la suivante : si vous continuez à jouer à ce jeu pour toujours, les nombres que vous créez se dispersent-ils uniformément dans le terrain de jeu, ou s'agglutinent-ils dans un coin, laissant de vastes espaces vides ?

Ce document spécifique s'attaque à un casse-tête qui a commencé par une règle simple : partez des nombres 2 et 3. Ensuite, prenez n'importe quels deux nombres différents que vous possédez déjà, multipliez-les et soustrayez 1. Si le résultat est un nombre entier, ajoutez-le à votre collection. Répétez l'opération indéfiniment. La question, posée par le légendaire mathématicien Paul Erdős (qui l'a entendue de la part de l'auteur des célèbres séquences « Hofstadter's Figure-Figure »), est de savoir si cette collection de nombres est assez « épaisse ». Possède-t-elle une « densité inférieure positive » ? En langage clair, est-ce que l'ensemble de nombres que vous générez finit par remplir un pourcentage significatif et non nul de la droite numérique, peu importe jusqu'où vous allez ? Pendant longtemps, personne ne savait si la réponse était oui ou non.

La Solution : Un Système de Trafic pour les Nombres

Dans cet article, Samuel Korsky prouve que la réponse est oui. L'ensemble de nombres générés par cette règle possède effectivement une densité inférieure positive. Cela signifie que lorsque vous observez des intervalles de nombres de plus en plus grands, vous trouverez toujours un bloc garanti, non nul, de ceux-ci appartenant à cet ensemble spécial. Ce n'est pas seulement quelques nombres éparpillés ; ils sont abondants.

Pour comprendre comment l'auteur a résolu cela, imaginez l'ensemble de nombres comme une ville, et la règle « multiplier et soustraire 1 » comme un ensemble de rues à sens unique. L'objectif de l'auteur était de montrer qu'il existe tellement de façons différentes de conduire à travers cette ville que vous ne pouvez pas éviter d'atteindre beaucoup de destinations. Cependant, il y a un piège : la règle stipule que vous ne pouvez multiplier que des nombres distincts. Si vous essayez de multiplier un nombre par lui-même, la règle se brise. C'est comme une loi de circulation qui stipule que vous ne pouvez pas rouler sur une route si vous avez déjà été sur ce même segment de route au cours du même trajet.

La stratégie de l'auteur consiste à construire un « système de contrôle du trafic » en utilisant une carte divisée en 20 zones spécifiques (intervalles). Il assigne différents « multiplicateurs » (comme 2, 3, 5, 9, 14) à ces zones. Lorsqu'un nombre atterrit dans une zone, le système lui indique quel multiplicateur utiliser ensuite. Le génie de la preuve réside dans la manière dont ces multiplicateurs sont choisis. L'auteur met en place quatre différents « modèles de trafic » (assignations). En basculant entre ces modèles en fonction de l'état actuel du système, il s'assure que les nombres ne restent pas bloqués ou ne violent pas la règle de « distinction ».

Pensez à cela comme à un jeu de « Suivez le chef » où le chef essaie de maintenir un équilibre parfait. L'auteur suit les « ingrédients » des nombres (spécifiquement les puissances des nombres premiers 2, 3, 5 et 7). Il veut que la recette reste équilibrée afin que les nombres croissent d'une manière très spécifique et prévisible. Il utilise une boucle de rétroaction : si la recette devient trop lourde en nombre 2, le système bascule vers un modèle qui ajoute plus de 3 ou de 5 pour équilibrer. Cela permet de maintenir la « pente » de la croissance (la vitesse à laquelle les nombres deviennent plus grands) verrouillée sur une cible spécifique.

L'article montre qu'en gérant soigneusement ces changements, le système crée un nombre massif de chemins uniques qui aboutissent tous à la même « pente ». Parce que les chemins sont uniques et que le système est conçu pour revenir à son point de départ de manière répétée (un concept appelé « récurrence positive »), les mathématiques prouvent qu'il existe une infinité de nombres distincts générés.

Crucialement, l'auteur prouve que ces chemins sont distincts bien que les mathématiques sous-jacentes permettent certains chevauchements (le système n'est pas « libre » au sens mathématique strict). Il le fait en montrant que si l'on remonte les chemins à rebours sur sa carte de 20 zones, ils ne se croisent jamais avant d'atteindre la toute fin. Cela garantit que chaque chemin produit un nombre final unique.

La conclusion finale est un argument de comptage. L'auteur calcule que pour chaque « étape » de ce processus, le nombre de chemins valides croît à un rythme qui correspond à la croissance des nombres eux-mêmes. Il prouve que pour un grand nombre $x$ spécifique, la quantité de son ensemble spécial trouvée entre $1$ et $x$ est au moins $c \times x$, où $c$ est une constante supérieure à zéro. En d'autres termes, peu importe jusqu'où vous comptez, vous trouverez toujours un flux constant de ces nombres.

L'article ne se contente pas de suggérer que c'est probable ; il fournit une preuve mathématique rigoureuse, étape par étape. Il utilise une combinaison de probabilité (pour montrer que le système revient toujours à son point de départ), de géométrie (pour cartographier les intervalles) et de théorie des nombres (pour compter les facteurs premiers). Le résultat est une réponse définitive à une question vieille de plusieurs décennies : l'ensemble n'est pas épars ; il est dense, remplissant la droite numérique d'une présence positive et fiable.