LA PREUVE D'UNE IA, REDESSINÉE POUR LES HUMAINS

Dessinez des points et reliez-en certains par des traits. Les mathématiciens appellent cela un graphe ; les points sont des sommets, les traits des arêtes, et le nombre de traits qui touchent un point est son degré. Un arbre est un graphe d’un seul tenant sans boucle, comme une brindille ramifiée ; un arbre à t points a toujours t − 1 traits.

Au début des années 1960, Paul Erdős et Vera T. Sós ont posé une question simple : combien de traits obligent un graphe à contenir tous les arbres d’une taille donnée ? Leur réponse, la conjecture d’Erdős–Sós, est la suivante :

Si un graphe a un degré moyen supérieur à t − 2, il contient tous les arbres à t sommets.

Le seuil est exact. Prenez des copies séparées d’un graphe complet à t − 1 points, chaque paire reliée : chaque point a exactement t − 2 voisins, et pourtant aucun morceau n’est assez grand pour contenir un arbre à t points. La difficulté tient au mot moyen. Si chaque point avait au moins t − 1 voisins, on pourrait placer un arbre branche par branche sans souci. Mais une moyenne ne dit rien d’un point en particulier : certains peuvent avoir des centaines de voisins, d’autres presque aucun.

Soixante ans de réponses partielles

Selon l’historique retracé dans l’article, le problème date de 1962-1964 et est devenu central dans la branche des mathématiques qui étudie combien d’arêtes imposent un motif donné. Des cas particuliers sont tombés : étoiles, chemins, étoiles doubles, arbres à peu de branches. Au début des années 1990, quatre mathématiciens — Ajtai, Komlós, Simonovits et Szemerédi — ont annoncé une preuve pour les très grands arbres, mais des articles récents notent qu’aucun manuscrit complet n’a jamais été publié. D’autres résultats partiels sont venus en 2021, 2024 et 2026. Le 4 septembre 2026, Reed et Stein ont publié une preuve pour les grands graphes denses, qu’ils disent avoir développée sans IA.

Puis est arrivé un rapport. En septembre 2026, Tom Adamczewski et Thomas Bloom, dans un document intitulé FrontierMath Erdős, ont attribué une preuve de la conjecture complète à une version en préversion d’un modèle d’IA, GPT-6 Astra. L’argument de comptage original est public, et un dépôt associé documente la recherche autonome de la preuve par l’IA et une vérification formelle dans Lean, un langage de vérification de preuves. Les auteurs du rapport ont aussi appelé des experts humains à rédiger des exposés traditionnels plus complets.

Dévoiler un graphe un point à la fois

Jay Cummings, de l’université d’État de Californie à Sacramento, répond à cet appel. Son article de 27 pages garde l’argument de comptage central de l’IA mais change la façon de le raconter :

1. Dévoiler le graphe peu à peu. Ranger les sommets dans un certain ordre et les découvrir un par un, avec les arêtes entre ceux déjà montrés.
2. Demander plus. Au lieu de n’importe quelle copie de l’arbre, en chercher une dont la « racine » choisie tombe sur le tout premier sommet. Demander plus rend la preuve plus facile.
3. Compter les voisins précoces. Ce sont les voisins du premier sommet qui apparaissent avant une telle copie. Les additionner sur tous les ordres possibles.
4. Borner le total. En échangeant des sommets ou des blocs entiers de l’ordre — des mouvements qu’on peut toujours défaire —, Cummings montre qu’en moyenne sur tous les ordres, il y a au plus t − 2 voisins précoces.

La dernière étape est courte. Si le graphe ne contenait aucune copie de l’arbre, chaque voisin du premier sommet serait précoce, dans tous les ordres. En moyenne sur tous les ordres, cela donne exactement le degré moyen — qui, par hypothèse, dépasse t − 2. Contradiction : l’arbre doit être là.

La preuve n’utilise que le total des degrés, pas leur répartition. Cummings en donne aussi une version probabiliste, et déroule des arbres à quatre et cinq sommets sur des graphes concrets.

Une preuve en livre d’images

L’article contient 32 figures. Il se termine par une conséquence classique : coloriez tous les traits d’un graphe complet avec q couleurs, et une couleur contiendra toujours un arbre donné dès que le graphe a q(t − 2) + 2 sommets. Dans une déclaration finale, Cummings explique avoir développé le texte dans un long dialogue avec ChatGPT, que les nouvelles idées de présentation — voisins précoces, découpages explicites, dessins — sont les siennes, et qu’il a tout vérifié et en prend l’entière responsabilité.

Il compare son exposé à d’autres récents, de Riordan et Scott, de Wood et de Frederickson, et note que la méthode a déjà été étendue aux réseaux orientés et aux « hypergraphes », certaines de ces extensions étant elles aussi attribuées à GPT-6 Astra. Sa contribution, écrit-il, est « une exposition visuelle de l’argument, centrée sur le lecteur, et non une nouvelle résolution de la conjecture ».