La conjecture du coureur solitaire est vérifiée pour huit coureurs

Informations de base

• ID de l'article: 2509.14111
• Titre: The lonely runner conjecture holds for eight runners
• Auteur: Matthieu Rosenfeld (LIRMM, Univ Montpellier, CNRS, Montpellier, France)
• Classification: math.CO cs.DM math.NT
• Date de publication: 17 octobre 2025
• Lien de l'article: https://arxiv.org/abs/2509.14111

Résumé

Cet article démontre que la conjecture du coureur solitaire est vérifiée pour le cas de 8 coureurs. La preuve repose sur la vérification informatique et sur des résultats récents permettant de borner la taille des contre-exemples minimaux. L'auteur indique que cette méthode s'applique également aux cas connus de 4, 5, 6 et 7 coureurs, et estime que de légères améliorations de la méthode suffiraient pour résoudre les cas de 9 ou 10 coureurs.

Contexte et motivation de la recherche

Définition du problème

La conjecture du coureur solitaire est un problème ouvert célèbre en théorie combinatoire des nombres et en approximation diophantienne, initialement proposé par Wills en 1965 sous une forme purement théorique des nombres. L'interprétation en termes de coureurs est la suivante : considérons k+1 coureurs possédant des vitesses constantes distinctes courant sur une piste circulaire de longueur unité. La conjecture du coureur solitaire affirme que pour chaque coureur, il existe un moment où ce coureur se trouve à une distance d'au moins 1/(k+1) de tous les autres coureurs.

Formulation mathématique

Conjecture 1 (Conjecture du coureur solitaire): Pour tous les entiers k≥1, pour chaque ensemble de k+1 entiers distincts v₁,...,vₖ₊₁, pour tous les i, il existe un nombre réel t tel que pour chaque j, $\|tv_i - tv_j\| \geq \frac{1}{k+1}$

où ‖x‖ désigne la distance de x à l'entier le plus proche.

Importance de la recherche

1. Signification théorique: Cette conjecture établit des connexions entre la théorie combinatoire des nombres, l'approximation diophantienne et les problèmes de visibilité
2. Défi computationnel: La difficulté de vérification croît de manière exponentielle avec le nombre de coureurs
3. Valeur applicative: Possède des applications importantes en théorie des graphes, théorie des nombres et optimisation combinatoire

Progrès de la recherche existante

• k=2: Cas trivial
• k=3: Résolu par Betke et Wills, ainsi que par Cusick
• k=4: D'abord prouvé par preuve assistée par ordinateur, puis simplifié
• k=5: Démontré par Bohman, Holzman et Kleitman
• k=6: Établi par Barajas et Serra
• k=7: Cas à démontrer dans cet article

Contributions principales

1. Résultat principal: Démonstration que la conjecture du coureur solitaire est vérifiée pour 8 coureurs (k=7)
2. Méthode unifiée: Proposition d'un cadre de preuve unifié applicable à tous les cas k=4,5,6,7
3. Techniques computationnelles: Développement d'algorithmes de vérification informatique efficaces utilisant le retour arrière et l'élagage
4. Outils théoriques: Établissement du lemme clé 6, fournissant une méthode systématique pour trouver les facteurs premiers dans les contre-exemples
5. Extensibilité: Fourniture d'une voie technique viable pour résoudre les cas k=8,9

Détails de la méthode

Stratégie centrale

La preuve utilise le raisonnement par l'absurde combiné à la vérification informatique:

1. Supposer l'existence d'un contre-exemple pour k=7
2. Utiliser le résultat de Malikiosis et al. pour borner le produit des vitesses dans le contre-exemple
3. Vérifier informatiquement que le produit des vitesses du contre-exemple doit être divisible par certains nombres premiers
4. Démontrer que le produit de ces nombres premiers dépasse la borne, produisant une contradiction

Résultats théoriques clés

Théorème 2 (Borne de Malikiosis-Santos-Schymura): Si la conjecture du coureur solitaire est vérifiée pour k, alors pour tous les k-uplets satisfaisant gcd(v₁,...,vₖ)=1 et $\sum_{S\subseteq\{1,...,k\}} \gcd(\{v_i : i \in S\}) > \binom{k+1}{2}^{k-1}$ la conjecture est également vérifiée pour k+1.

Corollaire 3: Si la conjecture du coureur solitaire est vérifiée pour k, alors pour tous les k-uplets satisfaisant gcd(v₁,...,vₖ)=1 et $\prod_{i\in\{1,...,k\}} v_i \geq \left[\frac{\binom{k+1}{2}^{k-1}}{k}\right]^k$ la conjecture est également vérifiée pour k+1.

Méthode de recherche des facteurs premiers

Lemme 4: Si {v₁,...,vₖ} ne possède pas la propriété LR, alors lcm(2,...,k+1) divise ∏vᵢ.

Lemme 6 (Outil central): Soit k≥3 et supposons que la conjecture du coureur solitaire soit vérifiée pour k-1. Soit p∈ℕ un entier positif. Si pour tous v₁,...,vₖ∈{0,...,(k+1)p-1} satisfaisant certaines conditions il existe un t approprié, alors pour tout k-uplet {v₁,...,vₖ} ne possédant pas la propriété LR, p divise ∏vᵢ.

Algorithme de vérification informatique

Transformation du problème: Conversion de la vérification du lemme 6 en problème de couverture d'ensemble:

• Définition de la relation de "couverture": v couvre j si et seulement si ‖jv/((k+1)p)‖ < 1/(k+1)
• Recherche de l'existence d'une couverture "mauvaise" violant les conditions du lemme 6

Techniques d'optimisation:

1. Précalcul des relations de couverture, stockage utilisant des vecteurs de bits
2. Algorithme de retour arrière pour construire les k-uplets avec élagage opportun
3. Exploitation de la symétrie pour réduire l'espace de recherche
4. Traitement prioritaire des éléments les plus difficiles à couvrir

Configuration expérimentale

Paramètres de vérification informatique

Pour le cas k=7:

• Borne supérieure: P ≤ 7.4×10⁵⁴
• Ensemble de nombres premiers de vérification S = {31, 37, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163}
• La vérification du plus grand nombre premier p=163 nécessite environ 32 heures de temps de calcul

Détails d'implémentation

• Langage de programmation: C++
• Structures de données clés: Vecteurs de bits (bitsets) pour les opérations binaires efficaces
• Algorithme: Recherche par retour arrière avec élagage
• Plateforme de calcul: Cœur de processeur unique

Résultats expérimentaux

Résultats principaux

Théorème 1: Pour tous les ensembles d'entiers de taille 7 {v₁,...,v₇}, il existe un nombre réel t tel que pour tous les i, ‖tvᵢ‖ ≥ 1/8.

Processus de preuve

1. Calcul de la borne supérieure: Par le corollaire 3, P < 7.4×10⁵⁴
2. Construction de la borne inférieure:
   • Par le lemme 4: P est divisible par lcm({2,3,4,5,6,7,8})
   • Par vérification informatique: P est divisible par tous les nombres premiers de l'ensemble S
   • Par conséquent, P est divisible par lcm({2,3,4,5,6,7,8}∪S) ≈ 1.82×10⁵⁵
3. Contradiction: La borne inférieure dépasse la borne supérieure, donc aucun contre-exemple n'existe

Résultats étendus

L'auteur démontre que la même méthode s'applique aux cas k=3,4,5,6:

Travaux connexes

Développement historique

1. Wills (1965): Première proposition de la conjecture sous forme théorique des nombres
2. Cusick: Proposition d'une formulation équivalente en termes de visibilité
3. Goddyn: Proposition de l'interprétation en termes de coureurs et du nom actuel
4. Tao (2019): Démonstration de l'existence de constantes calculables telles que la vérification finie suffit pour déterminer la conjecture

Résultats partiels

• Séquences à écarts: La conjecture est vérifiée pour les séquences possédant des écarts suffisants
• Résultat de Dubickas: La conjecture est vérifiée lorsque vⱼ₊₁/vⱼ ≥ 1 + 8e log k/k
• Amélioration de cet article: Réduction de la constante à 3e

Conclusion et discussion

Conclusions principales

1. La conjecture du coureur solitaire est vérifiée pour 8 coureurs
2. Fourniture d'un cadre de preuve unifié applicable à plusieurs cas
3. Développement d'une méthode de vérification informatique extensible

Limitations

1. Complexité computationnelle: Avec l'augmentation de k, les nombres premiers p nécessaires augmentent, et le temps de calcul croît de manière exponentielle
2. Dépendance informatique: Les étapes clés de la preuve nécessitent une vérification informatique substantielle
3. Défis d'extensibilité: Les cas k=8,9 nécessitent des ressources informatiques plus importantes

Directions futures

1. Optimisation algorithmique: Utilisation de solveurs plus avancés en remplacement de l'algorithme de retour arrière actuel
2. Améliorations théoriques: Recherche de variantes du lemme 6 ou de conditions d'élagage plus fortes
3. Preuve générale: Exploration de l'existence d'une preuve théorique valable pour tous les k

Évaluation approfondie

Points forts

1. Percée importante: Première démonstration du cas k=7, progrès significatif dans ce domaine
2. Innovation méthodologique: Approche ingénieuse combinant bornes théoriques et vérification informatique
3. Technique solide: Conception soignée des algorithmes de vérification informatique avec optimisations complètes
4. Cadre unifié: Fourniture d'une méthode générale pour traiter plusieurs cas
5. Implémentation open source: Fourniture d'une implémentation complète du code pour vérification et extension

Insuffisances

1. Dépendance informatique: La preuve dépend fortement de la vérification par ordinateur, manquant de l'élégance d'une preuve purement théorique
2. Restrictions d'extensibilité: La complexité computationnelle de la méthode limite l'extension à des valeurs plus grandes de k
3. Optimisation des constantes: Les bornes théoriques pourraient ne pas être suffisamment serrées, laissant place à des améliorations

Impact

1. Contribution académique: Fourniture d'une nouvelle approche pour un problème ouvert de longue date
2. Mathématiques computationnelles: Démonstration d'un exemple de résolution de problèmes difficiles combinant théorie et calcul
3. Recherches ultérieures: Fourniture d'une base technique pour les cas k≥8

Domaines d'application

Cette méthode s'applique à:

1. Des problèmes similaires en théorie combinatoire des nombres
2. Des conjectures mathématiques nécessitant une vérification finie
3. Des problèmes en théorie computationnelle des nombres et approximation diophantienne

Références bibliographiques

L'article cite 23 références pertinentes, couvrant le développement historique de la conjecture du coureur solitaire, les progrès théoriques et les méthodes computationnelles, fournissant aux lecteurs un contexte de recherche complet.

Évaluation technique: Cet article est un travail mathématique de haute qualité qui, par une analyse théorique innovante et une vérification informatique soigneusement conçue, résout avec succès un problème difficile ouvert depuis longtemps. Bien que dépendant de la vérification informatique, la méthode est rigoureuse et fiable, posant une base importante pour le développement ultérieur de ce domaine.