🔢 mathematics

New lower bounds for the degree/diameter problem via interaction with a browser-accessible LLM

Cet article présente de nouvelles bornes inférieures pour le problème degré/diamètre, spécifiquement $N(12,5)\ge 34{,}992$ et $N(16,5)\ge 147{,}456$ , obtenues grâce à un nouveau processus de découverte où l'auteur a interagi directement avec un LLM standard accessible via le Web pour construire des graphes explicites sans utiliser de cadres d'agents personnalisés ou de stratégies de recherche prédéfinies.

Auteurs originaux : Ryosuke Mizuno

Publié 2026-06-16

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Ryosuke Mizuno

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

La vue d'ensemble : Un casse-tête mathématique et un partenaire numérique

Imaginez un puzzle géant appelé le problème du degré/diamètre. Le but est de construire la plus grande « ville » possible (un réseau de points et de lignes) en respectant strictement deux règles :

La règle du degré : Chaque bâtiment (point) peut avoir au plus un certain nombre de routes (lignes) le reliant.
La règle du diamètre : Peu importe les deux bâtiments que vous choisissez, vous devez pouvoir aller de l'un à l'autre en un nombre très court d'étapes (pas plus de 5 étapes).

Les mathématiciens tentent depuis des décennies de construire les plus grandes villes possibles respectant ces règles. Plus la ville est grande, meilleur est le score.

La percée :
Cet article rapporte qu'un chercheur, travaillant seul avec un navigateur web standard et un agent conversationnel IA (ChatGPT), a construit deux nouvelles « villes » qui sont nettement plus grandes que celles connues précédemment.

Ville A : Un réseau de 34 992 bâtiments.
Ville B : Un réseau de 147 456 bâtiments.

Ces deux villes respectent la règle selon laquelle on peut aller n'importe où en 5 étapes ou moins, et aucun bâtiment n'a plus de 12 ou 16 routes, respectivement. Ces chiffres battent les précédents records mondiaux.

Comment ils ont fait : Le « Contrôleur » et la « Fibre »

Le secret de la construction de ces villes massives n'était pas seulement de deviner. Le chercheur et l'IA ont découvert une manière astucieuse de diviser le problème en deux morceaux plus petits et gérables. Voyez cela comme la construction d'une immense chaîne d'hôtels :

Le Contrôleur (Le plan) : Imaginez une carte petite et simple de quelques hubs clés. C'est le « Contrôleur ». Son rôle est de déterminer la direction générale. Dans ce cas, l'IA a trouvé une petite carte de 144 hubs qui garantit que l'on peut aller de n'importe quel hub à n'importe quel autre en exactement 5 étapes sans jamais faire demi-tour immédiatement (une marche « sans retour »).
La Fibre (Les chambres) : Maintenant, imaginez qu'à chaque hub de cette petite carte, vous n'avez pas seulement un bâtiment. Au lieu de cela, vous avez une tour de chambres complexe et massive. C'est la « Fibre ». L'IA a conçu un « système d'ascenseur » mathématique (utilisant l'algèbre et les corps finis) qui vous indique exactement comment passer d'une chambre à une autre dans ces tours en fonction de la route que vous empruntez.

Le tour de magie :
Le génie de la découverte fut de réaliser que si l'on obtient la petite carte (le Contrôleur) correctement, et que l'on obtient le système d'ascenseur (la Fibre) correctement, on peut les combiner pour créer une ville géante. La petite carte gère la navigation de la « vue d'ensemble », et le système d'ascenseur gère les « détails précis » du mouvement entre des millions de points spécifiques.

La collaboration Humain-IA : Une danse de guidage

Cet article est unique car il ne prétend pas que l'IA a résolu les mathématiques seule, ni que l'humain l'a fait seul. Il décrit une manière spécifique dont ils ont travaillé ensemble :

Pas de super-système : Le chercheur n'a pas construit de robot complexe ou de moteur logiciel spécialisé. Il a simplement utilisé le site web standard de ChatGPT, comme n'importe qui d'autre.
L'humain comme capitaine : Le chercheur agissait comme un capitaine de navire. Il n'a pas dit à l'IA comment construire l'ascenseur ou à quoi le plan devrait ressembler. Au lieu de cela, il a donné des instructions de haut niveau telles que :
- « Ne te contente pas de copier de vieilles idées. »
- « Si nous arrivons dans une impasse, arrête-toi et repense toute la stratégie. »
- « Donne-moi une raison de croire que cette nouvelle idée fonctionnera avant que nous ne tentions de la construire. »
L'IA comme exploratrice : L'IA a exploré des milliers de possibilités mathématiques. Elle a essayé de nombreuses idées qui ont échoué. Quand elle était bloquée, le capitaine humain disait : « Arrête, ce chemin est une impasse. Essaie un autre angle. »

Le moment « Eurêka ! » :
Pendant longtemps, l'IA essayait de corriger de petites erreurs dans de mauvais designs (comme colmater une fuite sur un bateau). Le capitaine humain a stoppé cela et a demandé un « nouveau principe ». L'IA a alors proposé l'idée du Contrôleur/Fibre (le système d'ascenseur de la carte de route). Ce fut le moment où l'abstraction est apparue. Une fois ce nouveau principe trouvé, le reste consistait à affiner les détails pour battre les records.

Ce que cet article NE prétend PAS

Il est important de s'en tenir à ce que l'article dit réellement :

Ce n'est pas une preuve générale que l'IA peut résoudre tous les problèmes mathématiques. Il s'agit d'un cas d'étude spécifique.
Cela ne concerne pas les applications médicales ou cliniques. Il s'agit purement de théorie des graphes (mathématiques).
Il ne s'agit pas de l'IA écrivant l'article final. Le chercheur humain a vérifié chaque étape, rédigé les preuves et assumé la responsabilité du résultat final. L'IA était un outil de découverte, pas l'auteur.

Résumé

Considérez cet article comme le journal de bord d'une expédition réussie. Un explorateur humain a utilisé une boussole numérique (l'IA) pour naviguer dans une jungle mathématique. L'explorateur n'a pas laissé la boussole conduire la voiture ; il l'a dirigée, lui a dit quand s'arrêter et lui a demandé de chercher de nouveaux itinéraires. Ensemble, ils ont trouvé un chemin vers une structure mathématique massive et jusque-là inconnue, prouvant qu'une IA standard via un navigateur web, lorsqu'elle est guidée par un humain doté d'une stratégie claire, peut aider à battre des records mondiaux en mathématiques pures.

Résumé Technique : Nouvelles bornes inférieures pour le problème du degré/diamètre via l'interaction avec un LLM accessible via navigateur

Énoncé du problème
Le document traite du problème du degré/diamètre, qui cherche à déterminer $N(\Delta, D)$ , le nombre maximal de sommets dans un graphe connexe simple et non orienté ayant un degré maximal d'au plus $\Delta$ et un diamètre d'au plus $D$ . Bien que la borne de Moore fournisse une limite supérieure pour $N(\Delta, D)$ , la valeur exacte demeure inconnue pour la plupart des paires de paramètres. L'accent est mis ici sur l'amélioration des bornes inférieures connues pour le diamètre $D=5$ avec des degrés maximaux $\Delta=12$ et $\Delta=16$ .

Méthodologie
L'étude documente un processus de découverte mathématique mené à travers un long dialogue avec un grand modèle de langage (LLM) accessible via un navigateur (ChatGPT, identifié comme gpt-5-5-pro dans les métadonnées) via son interface web standard. Crucialement, l'auteur n'a employé aucune couche d'orchestration externe, aucun cadre d'agent personnalisé, ni aucun assistant de preuve formelle. La recherche reposait uniquement sur les capacités interactives du LLM et sur les interventions de méta-niveau de l'auteur.

Le processus de découverte impliquait :

Exploration initiale : Recensement de la littérature et tentative de diverses méthodes de construction (ex: levés de permutations, graphes de tension, graphes réguliers aléatoires), dont la plupart ont échoué à produire un certificat.
Changement d'abstraction : Une transition pivotale s'est produite lorsqu'un LLM a proposé un principe de « levé par diagramme de route » (route-chart lift). Cela a décomposé le problème en deux tâches de conception finie indépendantes :
- Problème du contrôleur : Construire un petit graphe auxiliaire (le « contrôleur ») où chaque paire de sommets est connectée par une marche sans retour de longueur spécifique.
- Problème du diagramme de fibre : Construire des données algébriques linéaires (un « diagramme de route ») sur un corps fini de telle sorte que des matrices de contrôlabilité spécifiques soient non singulières pour tous les mots réduits de la longueur cible.
Interventions de méta-niveau : L'auteur a guidé la recherche en imposant des contraintes (ex: éviter la recherche web, exiger des idées qui ne sont pas essentiellement contenues dans la littérature existante, et demander des raisons a priori du succès) et en intervenant lorsque la recherche dérivait vers de la réparation locale ou du tâtonnement (trial-and-error).

Principales contributions
Le document présente deux contributions primaires :

Amélioration des bornes inférieures mathématiques :
Les auteurs présentent des constructions explicites de graphes simples et non orientés qui établissent de nouvelles bornes inférieures :
- $N(12, 5) \ge 34\,992$ (améliorant le record précédent de 29 621).
- $N(16, 5) \ge 147\,456$ (améliorant le record précédent de 132 496).
Ces graphes sont construits en effectuant le levé d'un graphe contrôleur spécifique de 144 sommets (dérivé d'un multigraphe à 6 sommets via une affectation de tension $C_4 \times C_6$ ) en utilisant un diagramme de route universel sur les corps finis $\mathbb{F}_3$ et $\mathbb{F}_4$ , respectivement. Le diamètre est prouvé être exactement de 5.
Analyse de processus de la collaboration Humain-IA :
Le document fournit une analyse basée sur les transcriptions d'un processus de découverte mathématique mené sans automatisation externe. Il souligne comment les interventions de méta-niveau (telles que la demande de nouveaux principes ou l'arrêt des tentatives de réparation locale) ont aidé à orienter le LLM vers une abstraction réussie (le levé par diagramme de route) et une solution finale. Les auteurs soulignent que le LLM a agi comme un moteur de découverte interactif, tandis que l'auteur a vérifié toutes les affirmations, le code et les certificats.

Résultats
Les graphes construits $G_3$ (12-régulier, 34 992 sommets) et $G_4$ (16-régulier, 147 456 sommets) respectent la contrainte de diamètre de 5. Les améliorations représentent des augmentations d'environ 18,13 % et 11,29 % par rapport aux records précédents, respectivement. Les constructions sont vérifiées par le calcul fini des marches sans retour du contrôleur et la non-singularité des matrices de contrôlabilité pour tous les mots réduits de longueur 5.

Signification et revendications
Le document revendique modestement une importance dans deux domaines :

Mathématique : Il fournit les premières constructions explicites pour ces paramètres spécifiques, rapprochant les bornes inférieures connues des bornes supérieures de Moore.
Méthodologique : Il sert d'étude de cas démontrant qu'une découverte mathématique significative est possible en utilisant uniquement une interface de navigateur standard pour un LLM, sans systèmes d'agents complexes. Les auteurs déclarent explicitement qu'ils ne traitent pas le LLM comme un auteur ou un prouveur autonome ; le chercheur humain conserve l'entière responsabilité de la validité mathématique.

Le document ne prétend pas que cette stratégie spécifique est généralement efficace ou que le LLM possède des capacités de raisonnement mathématique général au-delà de cet exemple précis. Il se présente comme un rapport observationnel d'un cas unique de succès où le guidage humain et la génération par LLM se sont combinés pour résoudre un problème ouvert en théorie des graphes.

La vue d'ensemble : Un casse-tête mathématique et un partenaire numérique

Comment ils ont fait : Le « Contrôleur » et la « Fibre »

La collaboration Humain-IA : Une danse de guidage

Ce que cet article NE prétend PAS

Résumé

Articles similaires