🔢 mathematics

The lonely runner conjecture holds for nine runners

Cet article prouve que la conjecture du coureur solitaire est vraie pour neuf coureurs en affinant la méthode précédemment utilisée pour établir le résultat pour huit coureurs.

Auteurs originaux : Matthieu Rosenfeld

Publié 2026-01-28

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Matthieu Rosenfeld

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

Imaginez une piste de course circulaire. Sur cette piste, il y a plusieurs coureurs, chacun ayant une vitesse différente. Certains courent vite, d'autres lentement, et aucun ne partage exactement la même vitesse.

La Conjecture du Coureur Solitaire est une question mathématique concernant ces coureurs. Elle demande : Existe-t-il un moment dans le temps où chaque coureur est « solitaire » ?

Dans ce contexte, être « solitaire » signifie que chaque coureur est loin de tous les autres. Plus précisément, si vous imaginez la piste comme un cercle de circonférence 1, un coureur est solitaire s'il se trouve à une distance d'au moins $1/(k+1)$ de tous les autres coureurs (où $k$ est le nombre de coureurs). La conjecture affirme que, peu importe la façon dont vous choisissez les vitesses, il existera toujours un moment spécifique où cela se produira pour tout le monde simultanément.

Pendant longtemps, des mathématiciens avaient prouvé que c'était vrai pour des groupes de 3, 4, 5, eb 6, 7 et 8 coureurs. Mais pour 9 coureurs, cela restait un mystère.

La percée : Résolution du cas pour 9 coureurs

Dans cet article, l'auteur, Matthieu Rosenfeld, prouve que la conjecture est effectivement vraie pour 9 coureurs.

Voici comment il a procédé, expliqué à travers une analogie simple :

1. Le scénario « impossible »

Pour prouver la conjecture, l'auteur utilise un grand classique de la logique : la preuve par l'absurde.
Il commence par supposer le contraire : Supposons qu'il existe un groupe de 9 coureurs avec des vitesses spécifiques où ils ne peuvent jamais tous être solitaires en même temps.

Si un tel groupe de coureurs « mauvais » existait, leurs vitesses devraient être des nombres très spécifiques. L'article utilise une « clôture » mathématique (une formule) pour montrer que si ce mauvais groupe existe, le produit de leurs vitesses ne peut pas être trop grand. Cela fixe une limite supérieure sur la taille de ces nombres.

2. Le travail de détective sur la « divisibilité »

Ensuite, l'auteur agit comme un détective cherchant des indices. Il demande : Si ce groupe de coureurs « mauvais » existe, par quels nombres leurs vitesses doivent-elles être divisibles ?

Il utilise une série de règles logiques (appelées lemmes) pour découvrir que les vitesses de ces coureurs hypothétiques doivent être divisibles par une très longue liste de nombres spécifiques (comme 17, 19, 23, 29, etc., et même des puissances de nombres comme 64 et 81).

Voyez cela comme ceci : si vous avez un code secret (le produit des vitesses), l'auteur prouve que ce code doit contenir la « clé » pour 17, la « clé » pour 19, la « clé » pour 23, et ainsi de suite.

3. La contradiction

C'est ici que la magie opère.

La limite supérieure : La « clôture » de l'étape 1 dit que le produit total des vitesses doit être plus petit qu'un certain nombre énorme (appelons-le $X$ ).
La limite inférieure : Le « travail de détective » de l'étape 2 dit que le produit doit être divisible par une liste de nombres si grande que leur produit combiné est plus grand que $X$ .

C'est comme dire : « Ce bocal ne peut contenir que 100 billes », mais prouver ensuite que « Les billes à l'intérieur doivent peser assez pour remplir un bocal qui en contient 200 ».

Puisque le produit ne peut pas être à la fois plus petit que $X$ et plus grand que $X$ en même temps, l'hypothèse initiale doit être fausse. Il n'existe pas de tel groupe « mauvais » de 9 coureurs. Par conséquent, la Conjecture du Coureur Solitaire est vraie pour 9 coureurs.

Le rôle des ordinateurs

Vous vous demandez peut-être : « Comment a-t-il vérifié tous ces nombres ? »
L'article admet que vérifier chaque combinaison possible de vitesses à la main est impossible. L'auteur a écrit un programme informatique spécialisé pour effectuer le gros du travail.

Le problème : L'ordinateur devait vérifier si certains motifs complexes de nombres pouvaient « couvrir » une piste sans laisser d'espace vide (un endroit « solitaire »).
L'innovation : L'auteur n'a pas simplement utilisé des solveurs informatiques standards (qui sont comme utiliser un marteau-pilon pour casser une noix). Il a construit un algorithme de « backtracking » (retour sur trace) personnalisé et hautement efficace.
- Imaginez essayer de trouver un chemin à travers un labyrinthe. Au lieu de parcourir chaque chemin, son programme est assez intelligent pour réaliser : « Si je tourne à gauche ici, je vais heurter une impasse 10 étapes plus tard, donc je ne vais même pas me donner la peine de marcher jusque-là. »
- Cette optimisation a rendu l'ordinateur beaucoup plus rapide que les tentatives précédentes, faisant passer le temps pour des problèmes similaires de 32 heures à 50 minutes.

Qu'en est-il de 10 coureurs ?

L'article mentionne brièvement que, bien que la méthode pourrait théoriquement fonctionner pour 10 coureurs, les mathématiques deviennent incroyablement difficiles. La « clôture » devient beaucoup plus haute, et l'ordinateur devrait vérifier des nombres si grands qu'il faudrait environ deux ans à un seul cœur de processeur pour terminer le travail.

L'auteur note qu'un autre chercheur a résolu indépendamment le cas des 10 coureurs en utilisant une méthode de « criblage » légèrement différente et plus rapide, mais cet article se concentre strictement sur la preuve pour 9 coureurs et sur les améliorations spécifiques apportées à la logique et au code pour y parvenir.

Résumé

En bref, cet article résout un puzzle vieux de plusieurs décennies pour 9 coureurs en :

Supposant l'existence d'un groupe de coureurs « mauvais ».
Prouvant qu'un tel groupe nécessiterait des nombres mathématiquement impossibles (trop grands pour tenir dans l'espace autorisé).
Utilisant un programme informatique personnalisé et ingénieux pour vérifier les règles mathématiques qui mènent à cette contradiction.

Le résultat confirme que sur n'importe quelle piste avec 9 coureurs de vitesses différentes, il existe toujours un moment où tout le monde est parfaitement seul.

Résumé Technique : La Conjecture du Coureur Solitaire pour Neuf Coureurs

Énoncé du Problème
L'article traite de la Conjecture du Coureur Solitaire (Lonely Runner Conjecture), un problème ouvert de longue date en théorie combinatoire des nombres, proposé pour la première fois par Wills en 1967. La conjecture postule que pour tout entier $k \ge 1$ et pour tout ensemble de $k$ entiers distincts (représentant les vitesses des coureurs) $v_1, \dots, v_k$ , il existe un temps réel $t$ tel que chaque coureur est « solitaire ». Mathématiquement, cela signifie qu'il existe un $t$ où la distance de chaque coureur par rapport à l'origine sur un cercle unité est au moins de $1/(k+1)$ , exprimée par $\|t v_i\| \ge 1/(k+1)$ pour tout $i$ .

Bien que la conjecture ait été vérifiée pour de petites valeurs de $k$ (jusqu'à $k=7$ ), elle reste ouverte dans le cas général. Ce document cible spécifiquement le cas de neuf coureurs ( $k=9$ ).

Méthodologie
La stratégie de preuve s'appuie sur les travaux antérieurs de l'auteur établissant la conjecture pour huit coureurs. L'argument central repose sur une preuve par l'absurde impliquant les propriétés d'un hypothétique « contre-exemple minimal ».

Réduction aux Contraintes de Divisibilité :
La preuve utilise une borne dérivée de Malikiosis, Santos et Schymura (Théorème 1), qui implique que si la conjecture est vraie pour $k$ , elle l'est pour $k+1$ à condition que le produit des vitesses de tout contre-exemple minimal dépasse un certain seuil. Par conséquent, pour prouver la conjecture pour $k+1$ , il suffit de montrer qu'aucun ensemble de $k$ vitesses n'existe qui viole la « propriété du coureur solitaire » (propriété LR) tout en satisfaisant les contraintes de divisibilité imposées par la borne.
Lemme Généralisé pour les Diviseurs :
Les auteurs introduisent le Lemme 6, une version renforcée et généralisée d'un lemme précédent (Lemme 3). Ce lemme établit les conditions sous lesquelles un entier $d$ spécifique doit diviser le produit des vitesses de tout ensemble de 8 entiers qui ne possède pas la propriété LR.
- Le lemme introduit un coefficient $c$ et considère les vitesses modulo $9cd$.
- Il incorpore des conditions de divisibilité spécifiques concernant le nombre de vitesses divisibles par 3 et 9 (dérivées du Lemme 5).
- La condition nécessite de vérifier que pour tout ensemble de 8 vitesses satisfaisant des contraintes spécifiques de PGCD et de divisibilité, il existe un temps $t$ satisfaisant la propriété LR.
Vérification Assistée par Ordinateur (Reformulation en Problème de Couverture d'Ensemble) :
La vérification des conditions du Lemme 6 est intensément gourmande en calcul. Les auteurs reformulent le problème en tant que problème de couverture d'ensemble (Lemme 7).
- Un entier $v$ « couvre » un entier $j$ si $\| \frac{jv}{9cd} \| < 1/8$ .
- L'objectif est de vérifier qu'aucun $8$-uplet « mauvais » n'existe qui couvre tous les entiers nécessaires tout en satisfaisant les contraintes de divisibilité.
- Les auteurs ont implémenté un algorithme de backtracking avec des optimisations significatives par rapport à leur travail précédent pour $k=7$ $k = 7$ :
  - Précalcul des bitsets pour les positions couvertes.
  - Stratégies d'élagage basées sur le nombre maximal de nouveaux entiers qu'un élément candidat peut couvrir.
  - Mémoïsation pour éliminer les chemins de recherche redondants.
- Les auteurs ont également testé des approches de solveurs SAT (utilisant Cardinality-CDCL et Minicard) mais ont constaté qu'elles étaient nettement plus lentes que leur implémentation de backtracking personnalisée pour cette structure de problème spécifique.

Contributions Clés et Résultats

Preuve pour Neuf Coureurs : Le papier fournit une preuve complète que la Conjecture du Coureur Solitaire est vérifiée pour $k=9$ .
Identification des Diviseurs : En appliquant le Lemme 6 avec un programme informatique, les auteurs ont identifié un ensemble $S$ d'entiers (incluant des puissances de nombres premiers comme $64, 81, 25$ et des nombres premiers jusqu'à 191) qui doivent diviser le produit des vitesses dans tout contre-exemple minimal pour 9 coureurs.
Contradiction : Le produit des éléments de l'ensemble $S$ (qui sont premiers entre eux) est d'environ $9,09 \times 10^{79}$ . Cependant, la borne théorique supérieure pour le produit des vitesses dans un contre-exemple minimal (dérivée du Corollaire 2) est d'environ $8,47 \times 10^{79}$ . Puisque le produit requis des diviseurs excède le produit maximal possible des vitesses, aucun contre-exemple de ce type ne peut exister.
Améliorations Algorithmiques : Le document détaille les améliorations d'implémentation spécifiques qui ont réduit le temps d'exécution pour le cas de vérification $k=7$ de 32 heures à 50 minutes, permettant ainsi la vérification plus complexe pour $k=9$ .

Signification et Revendications
Les auteurs affirment que ce résultat étend la portée connue de la Conjecture du Coureur Solitaire de 7 à 9 coureurs. Ils notent que la technique utilisée est théoriquement applicable à n'importe quel nombre de coureurs, bien que le coût computationnel croisse rapidement.

Indépendance : Les auteurs reconnaissent que Trakulthongchai a annoncé indépendamment des preuves pour $k=9$ et $k=10$ peu avant cette soumission. Le travail de Trakulthongchai s'appuie également sur la preuve pour $k=7$ et utilise une « approche de criblage ingénieuse » qui semble être environ 100 fois plus rapide que la méthode présentée ici.
Perspectives Futures : Le papier discute de la faisabilité d'étendre cela à $k=10$ . Bien que la méthode soit adaptable, le coût de calcul pour vérifier les nombres premiers jusqu'à environ 263 est estimé à deux ans sur un seul cœur. Les auteurs suggèrent que la combinaison de leurs améliorations (comme la prise en compte des puissances de petits nombres premiers) avec l'approche de criblage de Trakulthongchai pourrait rendre le cas $k=10$ plus traitable, mais ils ne prétendent pas l'avoir résolu eux-mêmes.

En résumé, le papier résout avec succès le cas $k=9$ grâce à une combinaison de lemmes théoriques raffinés et d'une vérification informatique hautement optimisée, tout en positionnant modestement le travail comme une étape progressant de manière bénéfique vers la résolution de la conjecture pour un nombre plus élevé de $k$ .