L’IA trouve un contre-exemple à une conjecture de théorie des graphes vieille de 30 ans

L’IA apporte un défi à une affirmation de longue date en théorie des graphes

Une conjecture vieille de 30 ans en théorie des graphes serait tombée après qu’un système d’IA a généré un contre-exemple en quelques heures. Selon New Scientist, Dmitry Rybin, cofondateur de la start-up d’IA Autokernel, a utilisé ChatGPT 5.6 Pro pour rechercher un contre-exemple structuré à la conjecture de Dinitz-Garg-Goemans, un résultat qui était resté une question ouverte en combinatoire et en optimisation pendant des décennies.

Le rapport indique que Rybin a utilisé au total quatre prompts, soit moins de 60 mots, et que le modèle a passé environ 5,5 heures à chercher avant de renvoyer une construction montrant que la conjecture est fausse. Si le contre-exemple résiste à l’examen des experts, l’épisode marquerait un nouveau moment notable dans une tendance qui évolue rapidement : les systèmes d’IA ne se contentent pas d’aider aux démonstrations routinières ou à la manipulation symbolique, ils font de plus en plus émerger des objets nouveaux qui changent le statut de questions mathématiques établies.

Ce basculement compte, car les contre-exemples occupent une place particulière en mathématiques. Un théorème peut survivre à des années de vérification sur de nombreux cas particuliers, mais une seule exception valide suffit à faire s’effondrer l’énoncé général. Dans les domaines où l’intuition se construit à partir de motifs observés sur de petits exemples, trouver le premier objet qui brise une règle peut être étonnamment difficile. C’est précisément le type de problème de recherche où l’exploration automatisée à grande échelle peut avoir un avantage.

Ce que la conjecture cherchait à dire

La conjecture de Dinitz-Garg-Goemans relève de la théorie des graphes, l’étude de réseaux construits à partir de sommets et d’arêtes. New Scientist décrit l’énoncé au moyen d’une analogie logistique. Imaginez des expéditions quittant un entrepôt vers plusieurs destinations. Dans une version du problème, ces expéditions peuvent être divisées en plus petits morceaux et acheminées indépendamment. La conjecture avançait que cette configuration flexible pouvait être convertie en un autre arrangement où les expéditions restent indivisibles, sans augmenter le coût total.

Ce type d’énoncé est attrayant parce qu’il suggère qu’une optimisation du monde réel, souvent chaotique, peut parfois être réduite à des formes plus nettes et plus faciles à analyser. S’il était vrai, l’énoncé aurait impliqué un pont fiable entre des scénarios de flux divisés et non divisés. À l’inverse, le contre-exemple rapporté indique que ce pont n’existe pas toujours. Quelque part dans la structure de ces réseaux, il existe des cas où interdire la division modifie bien l’économie d’une manière que la conjecture disait impossible.

Pour les spécialistes, cela ne signifie pas que tout le domaine s’effondre. Cela signifie que la frontière se précise. Les chercheurs peuvent désormais demander où la conjecture échoue, si des versions restreintes tiennent encore, et quelles classes de graphes préservent le comportement souhaité. Une conjecture fausse crée souvent autant de travail productif qu’une conjecture vraie, car elle oblige le domaine à remplacer un principe large mais inexact par une cartographie plus précise.

Pourquoi ce cas attire l’attention

Une partie de la réaction tient à la simplicité apparente des prompts. Rybin a déclaré à X, comme le cite New Scientist, qu’il avait passé de nombreuses semaines à réfléchir lui-même au problème. Pourtant, les prompts décrits dans l’article étaient minimaux : une consigne initiale demandant de trouver un contre-exemple décisif, suivie de requêtes répétées pour continuer à chercher. Ce contraste est devenu central dans l’histoire. L’intérêt ne vient pas seulement du fait qu’une IA était impliquée, mais du fait que l’interface destinée à l’utilisateur semblait si ordinaire alors que la recherche computationnelle sous-jacente faisait peut-être quelque chose de non trivial.

Cette distinction est importante. Un prompt bref ne signifie pas que le processus de raisonnement était simple. Cela signifie que l’utilisateur n’a pas eu besoin de bricoler un flux de travail formel dense pour orienter le système vers une recherche utile. À mesure que les outils d’IA s’améliorent, le goulot d’étranglement pourrait passer de la spécification de chaque étape à la formulation de la bonne cible mathématique, à la vérification rigoureuse du résultat et à la traduction des objets produits par la machine en formes qu’une communauté de recherche puisse vérifier et exploiter.

New Scientist note aussi que c’est la deuxième fois en une semaine que l’IA est créditée pour avoir renversé une conjecture de longue date. L’article place le nouveau résultat en théorie des graphes aux côtés d’un contre-exemple antérieur généré par IA à la conjecture jacobienne, et renvoie à un modèle d’OpenAI qui aurait résolu en mai une conjecture vieille de plusieurs décennies posée par Paul Erdos. Pris ensemble, ces épisodes suggèrent que le moment actuel n’est pas une curiosité ponctuelle, mais une partie d’une accélération plus large des mathématiques assistées par machine.

Pourquoi la théorie des graphes peut être particulièrement exposée aux surprises

Chris Bowman-Scargill, de l’université de York, a déclaré à New Scientist qu’il existe une blague récurrente en mathématiques selon laquelle toute conjecture en théorie des graphes est fausse. L’humour reflète un véritable défi structurel. En théorie des graphes, un comportement qui paraît stable dans de petits exemples peut changer brutalement lorsqu’un ou deux sommets sont ajoutés. Cela rend la reconnaissance informelle de motifs moins fiable que dans les domaines où les exemples de bas rang tendent à refléter plus fidèlement les structures plus grandes.

Dans un tel contexte, les systèmes automatisés sont naturellement utiles. Ils peuvent aller au-delà de la plage qu’examinent les humains à la volée, énumérer des cas à grande échelle et rechercher des constructions étranges qui ne paraissent pas intuitives au premier abord. Un mathématicien peut avoir une bonne intuition conceptuelle de la raison pour laquelle un énoncé devrait être vrai, tandis qu’une machine peut tester sans relâche si cette intuition survit dans des recoins plus étranges de l’espace.

La leçon probable n’est pas que les mathématiciens deviennent obsolètes. Leur rôle change plutôt. Les humains décident encore quelles questions comptent, évaluent l’importance d’une construction, identifient la raison structurelle de son fonctionnement et transforment une sortie computationnelle brute en un récit mathématique robuste. Mais le paysage de la recherche évolue. Lorsque les machines peuvent faire émerger des exemples décisifs plus vite et plus souvent, la formulation même des conjectures peut devenir plus disciplinée et plus adversariale, les chercheurs s’attendant à un contrôle machine agressif dès les débuts d’une idée.

La suite

La question immédiate est celle de la vérification. Un contre-exemple allégué ne modifie l’état de l’art mathématique qu’après confirmation, par des experts, que l’objet viole bien la conjecture dans les conditions formelles exactes. New Scientist présente le résultat comme une avancée majeure, mais son importance à long terme dépendra de la façon dont la communauté le validera, l’interprétera et l’étendra.

Si le résultat tient, il renforcera une tendance que de nombreux chercheurs peinent déjà à intégrer. L’IA passe du statut d’assistant à celui de collaborateur dans les travaux orientés découverte, surtout dans les domaines où l’espace de recherche est vaste mais où la condition de succès est nette. Les mathématiques constituent un terrain d’essai particulièrement visible parce que les résultats peuvent, en principe, être vérifiés avec précision. Cela facilite la distinction entre le battage médiatique et le fond, davantage que dans bien d’autres disciplines intellectuelles.

Malgré tout, l’effet social pourrait dépasser la seule conjecture. Une génération de mathématiciens est désormais confrontée à l’idée que des intuitions précieuses peuvent émerger de systèmes sollicités en langage courant, fonctionnant pendant des heures et renvoyant des objets que les humains n’avaient pas pensé à construire. Que cela suscite malaise, enthousiasme ou les deux, cela marque un changement significatif dans la manière dont la découverte peut se produire.

Cet article s’appuie sur le reportage de New Scientist. Lire l’article original.