🔢 mathematics

A Distinct Covering System with Minimum Modulus 7 and Minimal Least Common Multiple 10080

Cet article infirme la conjecture de Klein en construisant un système de recouvrement distinct avec un module minimum de 7 et un plus petit commun multiple de 10080, tout en prouvant simultanément qu'un tel système ne peut exister avec un plus petit commun multiple grâce à un argument de filtrage à plusieurs étapes et une vérification computationnelle.

Auteurs originaux : Jiheng Zhang, Shiliang Zhang

Publié 2026-07-22

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Jiheng Zhang, Shiliang Zhang

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 la droite numérique comme une autoroute infinie s'étendant dans les deux sens, peuplée de tous les entiers de l'infini négatif à l'infini positif. Dans le monde des mathématiques, et plus précisément dans une branche appelée la théorie des nombres, il existe un puzzle fascinant sur la manière de « couvrir » toute cette autoroute en utilisant uniquement un ensemble de panneaux de signalisation. Ces panneaux sont des progressions arithmétiques. Pensez à un panneau qui dit : « Chaque 7e voiture est une voiture rouge », ou « Chaque 12e voiture est une voiture bleue ». Si vous placez suffisamment de ces panneaux à différents intervalles, vous pourriez peut-être garantir que chaque voiture sur l'autoroute est soit rouge, soit bleue (ou d'une autre couleur). Lorsque vous réussissez à couvrir chaque entier avec une collection de ces motifs répétitifs, vous avez créé un système de couverture.

Les règles du jeu deviennent plus strictes quand les mathématiciens demandent un système de couverture distinct. Cela signifie que chaque panneau doit avoir un intervalle unique ; vous ne pouvez pas avoir deux panneaux qui disent tous deux « chaque 7e voiture ». Vous devez utiliser des nombres différents pour vos intervalles, comme 7, 8, 9, 10, et ainsi de suite. Une question naturelle est de savoir à quel point le plus petit intervalle peut être petit. Pendant longtemps, les mathématiciens se sont demandé s'il existait une limite dure à la façon dont ce « modulo minimum » pouvait devenir petit. Récemment, il a été prouvé qu'il existe effectivement une limite, mais le mystère qui restait était celui de l'efficacité. Si vous fixez le plus petit intervalle (disons 7), quel est le plus petit « plus grand nombre » (le plus petit commun multiple) dont vous avez besoin pour faire fonctionner l'ensemble du système ? C'est comme demander : si votre pas le plus petit est de 7 enjambées, quelle distance devez-vous parcourir avant que votre motif de pas ne s'aligne parfaitement avec chaque position possible sur la route ?

Cet article traite de cette question exacte pour le cas spécifique où le plus petit intervalle est 7. Les auteurs, Shiliang Zhang et Jiheng Zhang, ont cherché à trouver l'absolu minimum du « plus grand nombre » requis pour construire un système de couverture distinct commençant par un pas de 7. Avant ce travail, un mathématicien nommé Klein avait construit un système fonctionnel avec un « plus grand nombre » de 15 120 et avait supposé que c'était le meilleur possible. Cependant, les auteurs de cet article prouvent que l'hypothèse de Klein était trop élevée. Ils ont construit un nouveau système, plus efficace, qui fonctionne avec un « plus grand nombre » de seulement 10 080. De plus, ils ont mathématiquement prouvé qu'il est impossible de le faire avec un nombre plus petit que 10 080. Ils n'ont pas seulement trouvé une meilleure solution ; ils ont prouvé que c'est la meilleure solution.

L'histoire de détective du nombre 10 080

Pour comprendre comment les auteurs ont résolu cela, imaginez que vous êtes un détective essayant de trouver une clé spécifique dans un immense entrepôt poussiéreux. L'entrepôt contient tous les « plus grands nombres » possibles (plus petit commun multiple) qui sont un multiple de 7 et qui se situent entre 5 040 et 10 080. Votre objectif est de prouver que chaque nombre dans cette plage est une « fausse clé » qui n'ouvrira pas la porte, tandis que le nombre 10 080 est la « vraie clé ».

Le premier filtre : La somme des inverses
Les auteurs commencent par appliquer un « filtre de somme des inverses ». Dans le langage courant, imaginez que chaque intervalle possible (comme 7, 8, 9) contribue un peu de « puissance de couverture » au système. La règle est que la puissance totale de tous vos intervalles choisis doit être supérieure à 1 pour couvrir toute l'autoroute. Si vous additionnez la « puissance » de chaque intervalle possible disponible pour un candidat spécifique et que le total est inférieur à 1, ce candidat est immédiatement disqualifié. Ce filtre a été très efficace, éliminant instantanément la plupart des nombres de l'entrepôt et ne laissant que 18 candidats suspects.

Le deuxième filtre : Le test de programmation en nombres entiers
Ensuite, les auteurs ont utilisé un outil informatique puissant appelé « programmation en nombres entiers ». Considérez cela comme un solveur de puzzles super organisé. Pour chacun des 18 candidats restants, l'ordinateur a essayé d'organiser les panneaux de signalisation (classes de résidus) pour voir s'ils pouvaient couvrir toute l'autoroute sans laisser de lacunes. L'ordinateur était assez intelligent pour ignorer les arrangements redondants (comme décaler tout le motif d'un pas, ce qui ne change pas le résultat). Ce filtre a été impitoyable ; il a éliminé 14 des 18 candidats, prouvant que peu importe la façon dont vous organisiez les panneaux pour ces nombres, vous laisseriez toujours des voitures non couvertes.

Le troisième filtre : La somme partielle
Quatre candidats restaient : 5 040, 7 560, 8 400 et 9 240. C'étaient les « cas difficiles ». Les auteurs ont réalisé que pour certains de ces nombres, on pouvait couvrir presque toute l'autoroute, ne laissant qu'une infime fraction de voitures non couvertes. Cela rendait les tests précédents délicats. Pour gérer cela, ils ont utilisé un « filtre de somme partielle ». Au lieu de supposer que les panneaux couvrent tout parfaitement, ils ont calculé exactement quelle part de l'autoroute la meilleure disposition d'un sous-ensemble de panneaux pouvait couvrir. Ils ont découvert que pour 8 400 et 9 240, même l'arrangement le plus optimiste de panneaux laissait une lacune trop grande pour être comblée par les panneaux restants. Ces deux nombres ont été éliminés.

L'affrontement final : Le calcul Gurobi
Il ne restait que deux suspects tenaces : 5 040 et 7 560. Ces nombres étaient si bons pour couvrir l'autoroute qu'ils pouvaient en couvrir plus de 96 % et 98 % respectivement, ne laissant qu'une lacune minuscule et difficile à trouver. Pour résoudre cela, les auteurs ont lancé des simulations informatiques massives et exhaustives à l'aide d'un logiciel appelé Guroksi. Ils n'ont pas seulement deviné ; ils ont vérifié chaque mode possible d'organiser les panneaux pour ces deux nombres. L'ordinateur a tourné pendant des milliers de secondes, vérifiant des millions de possibilités, et a finalement déclaré : « Inexploitable ». Cela signifie qu'il est mathématiquement impossible de couvrir l'autoroute avec un pas minimum de 7 en utilisant 5 040 ou 7 560 comme plus grand nombre.

Le vainqueur : 10 080
Après avoir éliminé tous les nombres plus petits, les auteurs se sont tournés vers 10 080. Ils n'ont pas seulement prouvé que c'était possible ; ils ont construit le système réel. Ils ont listé les intervalles spécifiques et les points de départ (comme « chaque 7e voiture commençant à 6 », « chaque 8e voiture commençant à 7 », et ainsi de suite) qui couvrent parfaitement toute la droite numérique. Ils ont vérifié que ce système fonctionne, prouvant que 10 080 est effectivement une solution de travail.

La conclusion

L'article conclut par une réponse définitive : le plus petit « plus grand nombre » possible pour un système de couverture distinct avec un pas minimum de 7 est exactement 10 080. Cela améliore le record précédent de 15 120. Les auteurs n'ont pas seulement trouvé un meilleur nombre ; ils ont prouvé qu'aucun nombre plus petit ne pourrait jamais fonctionner. Ils l'ont fait en éliminant systématiquement chaque possibilité, des vérifications mathématiques simples aux simulations informatiques complexes, ne laissant aucune pierre non retournée. Le résultat est un fait précis et prouvé dans le monde de la théorie des nombres, montrant que bien que vous puissiez vous approcher très près de la couverture de l'autoroute infinie avec des nombres plus petits, vous ne pouvez simplement pas le faire parfaitement avant d'atteindre 10 080.

Résumé Technique : Un système de recouvrement distinct avec un module minimum 7 et un plus petit commun multiple minimal de 10080

Énoncé du Problème
L'article traite du problème de la détermination du plus petit commun multiple (PPCM) possible, noté $L_{\min}(m)$ , pour un système de recouvrement distinct avec un module minimum $m$ prescrit. Un système de recouvrement distinct est une collection finie de progressions arithmétiques $\{a_i \pmod{m_i}\}$ avec des modules $m_i$ distincts deux à deux qui recouvrent tous les entiers. Alors que Hough (2015) a prouvé que le module minimum dans tout système de recouvrement distinct est borné par une constante absolue, les valeurs spécifiques de $L_{\min}(m)$ pour de petits $m$ ont fait l'objet de constructions et de vérifications explicites.

Avant ce travail, les valeurs pour $m \le 6$ étaient établies : $L_{\min}(3)=120$ , $L_{\min}(4)=360$ , $L_{\min}(5)=1440$ , et $L_{\min}(6)=5040$ . Pour $m=7$ , Klein (2024) a construit un système avec $L=15120$ et a conjecturé que celui-ci était minimal. Cet article vise à résoudre le cas $m=7$ en construisant un système avec un PPCM plus petit et en prouvant qu'aucun PPCM plus petit n'est possible.

Méthodologie
Les auteurs emploient une stratégie de filtrage successif pour éliminer les valeurs candidates pour le PPCM $L$ dans l'intervalle $5040 \le L < 10080$ . La preuve repose sur le principe de « complétion par les diviseurs » : si un système de recouvrement distinct existe avec un module minimum $m$ et un PPCM $L$ , on peut ajouter des classes de congruence arbitraires pour n'importe quel diviseur $d$ de $L$ (où $d \ge m$ ) sans détruire la propriété de recouvrement. Ainsi, pour prouver la non-existence pour un $L$ spécifique, il suffit de montrer que l'ensemble « complété par les diviseurs » $D_m(L) = \{d : d|L, d \ge m\}$ ne peut pas former un système de recouvrement.

Le processus de filtrage consiste en quatre étapes :

Filtre de Somme des Réciproques : Basé sur l'obstruction de Mirsky–Newman (Lemme 1), qui stipule que pour tout système de recouvrement distinct, $\sum 1/m_i > 1$ . Les auteurs calculent $S_7(L) = \sum_{d|L, d \ge 7} 1/d$ . Si $S_7(L) \le 1$ , $L$ est immédiatement écarté. Cela réduit l'espace de recherche de tous les multiples de 7 dans l'intervalle à 18 candidats.
Filtre de Programmation en Entiers (PE) : Pour les candidats restants, les auteurs formulent un problème de faisabilité de programmation entière binaire. Les variables $x_{m,a}$ indiquent si la classe de congruence $a \pmod m$ est sélectionnée. Les contraintes imposent exactement une classe par module et le recouvrement de toutes les résidus modulo $L$ . Pour réduire la symétrie, les auteurs appliquent des normalisations d'invariance par translation et de permutation de couches de résidus (Lemmes 2 et 3) afin de fixer des classes de congruence spécifiques (par exemple, $6 \pmod 7$ , $7 \pmod 8$ ) avant de résoudre. Ce filtre élimine 14 des 18 candidats.
Filtre de Somme Partielle : Pour les cas restants plus difficiles (spécifiquement 8400 et 9240), les auteurs affinent l'argument de la somme des réciproques. Au lieu de supposer que toutes les classes sélectionnées sont disjointes, ils calculent le recouvrement maximal $\alpha_A(L)$ d'un sous-ensemble de modules $A$ via une PE plus petite, puis ajoutent la contribution maximale théorique des modules restants $B$ . Si $\alpha_A(L) + \sum_{m \in B} 1/m < 1$ , le candidat est écarté. Cela élimine 8400 et 9240.
Calcul Complet Gurobi : Les deux derniers candidats, $L=5040$ et $L=7560$ , résistent au filtre de somme partielle car ils admettent des « quasi-recouvrements » (recouvrant >96% et >98% des résidus, respectivement). Ces cas sont résolus en exécutant des vérifications de faisabilité complètes à l'aide du solveur Gurobi (v13.0.1) sur les systèmes complets complétés par les diviseurs.

Contributions Clés et Résultats

Construction : Les auteurs construisent explicitement un système de recouvrement distinct avec un module minimum 7 et un plus petit commun multiple de 10080. Ce système se compose de 63 modules distincts, dont le plus petit est 7.
Preuve de Minimalité : L'article prouve que $L_{\min}(7) = 10080$ . En éliminant systématiquement tous les $L < 10080$ (spécifiquement les 18 candidats ayant survécu au filtre de somme initial), les auteurs démontrent qu'aucun système de recouvrement distinct avec un module minimum 7 ne peut avoir un PPCM inférieur à 10080.
Réfutation de la Conjecture : Le résultat infirme la conjecture de Klein selon laquelle 15120 était le PPCM minimal pour $m=7$ .
Données Computationnelles : L'article fournit un tableau complet des temps d'exécution Gurobi et des résultats pour tous les 18 candidats, y compris les deux cas les plus difficiles (5040 et 7560) qui ont nécessité respectivement environ 13 789 et 13 159 secondes pour prouver l'infaisabilité.

Signification
L'article établit la valeur exacte de $L_{\min}(7)$ , étendant la séquence connue des PPCM minimaux pour les systèmes de recouvrement distincts. Ce travail démontre l'efficacité de la combinaison de la théorie analytique des nombres (sommes de réciproques) et de l'optimisation combinatoire (programmation entière et branch-and-bound) pour résoudre des problèmes d'existence dans les progressions arithmétiques. Les auteurs notent que la difficulté rencontrée avec $L=5040$ et $L=7560$ — où les systèmes recouvrent presque tous les résidus mais échouent à couvrir le reste — suggère que les futures améliorations de la preuve de minimalité pour des modules plus élevés pourraient nécessiter des certificats hybrides plus tranchants, capables de distinguer les « quasi-recouvrements » des véritables systèmes de recouvrement sans dépendre uniquement de la vérification complète par branch-and-bound.

L'histoire de détective du nombre 10 080

La conclusion

Articles similaires