Un modèle OpenAI a réfuté une conjecture centrale en géométrie discrète

Depuis près de 80 ans, les mathématiciens étudient une question d’une simplicité trompeuse : si l’on place $n$ points dans le plan, combien de paires de points peuvent être exactement à la distance $1$ l’une de l’autre ?

Il s’agit du problème des distances unitaires dans le plan, posé pour la première fois par Paul Erdős en 1946. C'est l'une des questions les plus connues de la géométrie combinatoire, facile à énoncer et remarquablement difficile à résoudre. Le livre Research Problems in Discrete Geometry, publié en 2005 par Brass, Moser et Pach, le décrit comme « probablement le problème le plus connu (et le plus simple à expliquer) de la géométrie combinatoire ». Noga Alon, éminent spécialiste de combinatoire à Princeton, le décrit comme « l’un des problèmes préférés d’Erdős ». Erdős a même offert une récompense en argent pour résoudre ce problème.

Aujourd’hui, nous partageons une avancée majeure sur le problème des distances unitaires. Depuis les travaux originaux d’Erdős, l’idée dominante était que les constructions en « grille carrée » représentées plus bas étaient essentiellement optimales pour maximiser le nombre de paires à distance unitaire. Un modèle interne d’OpenAI a réfuté cette conjecture ancienne, en fournissant une famille infinie d’exemples qui apportent une amélioration polynomiale. La preuve a été vérifiée par un groupe de mathématiciens externes. Ils ont aussi rédigé un article complémentaire expliquant l’argument et apportant davantage d’éléments de contexte sur l’importance du résultat.

La manière dont ce résultat a été trouvé est également remarquable. La preuve provient d’un nouveau modèle de raisonnement généraliste, plutôt que d’un système entraîné spécifiquement pour les mathématiques, structuré pour explorer des stratégies de preuve, ou ciblé en particulier sur le problème des distances unitaires. Dans le cadre d’un effort plus large visant à tester si des modèles avancés peuvent contribuer à la recherche de pointe, nous l’avons évalué sur un ensemble de problèmes d’Erdős. Dans ce cas, il a produit une preuve qui résout ce problème ouvert.

Cette preuve constitue une étape importante pour les communautés des mathématiques et de l’IA. C’est la première fois qu’un problème ouvert majeur, central dans un sous-domaine des mathématiques, est résolu de manière autonome par l’IA. Cela démontre aussi la profondeur de raisonnement que ces systèmes prennent désormais en charge. Les mathématiques offrent un terrain d’essai particulièrement clair pour le raisonnement : les problèmes sont précis, les preuves potentielles peuvent être vérifiées, et un long argument ne fonctionne que si le raisonnement tient du début à la fin. La méthode par laquelle le problème a été résolu est elle aussi remarquable. La preuve mobilise, de façon inattendue, des idées sophistiquées de théorie algébrique des nombres pour traiter une question géométrique élémentaire.

Le médaillé Fields Tim Gowers, dans l’article complémentaire, qualifie le résultat de « jalon dans les mathématiques de l’IA ». Selon le grand théoricien des nombres Arul Shankar, « À mon avis, cet article montre que les modèles d’IA actuels vont au-delà du simple rôle d’assistants pour les mathématiciens humains : ils sont capables d’avoir des idées originales et ingénieuses, puis de les mener à bien ».

La preuve est disponible ici⁠(ouverture dans une nouvelle fenêtre). L’article complémentaire rédigé par d’éminents mathématiciens externes est disponible ici⁠(ouverture dans une nouvelle fenêtre). Vous pouvez trouver une version abrégée de la chaîne de pensée du modèle ici⁠(ouverture dans une nouvelle fenêtre).

Soit $u(n)$ le plus grand nombre possible de paires à distance unitaire parmi $n$ points du plan. Il est facile de construire des exemples atteignant un taux de croissance linéaire : placer $n$ points sur une ligne donne $n-1$ paires, tandis qu'une grille carrée en donne environ $2n$. La construction auparavant la mieux connue, issue d'une grille carrée redimensionnée, donne en fait encore plus  : $n^{1 + C / \log \log(n)}$ pour une constante $C$. Comme $\log \log(n)$ tend vers l'infini avec $n$, le terme additionnel dans l'exposant tend vers $0$, ce qui signifie que ces constructions n'obtiennent qu'une croissance légèrement plus rapide que linéaire. Pendant des décennies, on a largement cru que ce taux était essentiellement le meilleur possible et qu'aucune construction ne pouvait améliorer de façon significative la grille carrée. En termes techniques, Erdős conjecturait une borne supérieure de $n^{1+o(1)}$, où le terme additionnel $o(1)$ désigne une quantité qui tend vers $0$ avec $n$.

Notre nouveau résultat réfute cette conjecture. Plus précisément, pour une infinité de valeurs de $n$, la preuve construit des configurations de $n$ points avec au moins $n^{1+\delta}$ paires à distance unitaire, pour un certain exposant fixe $\delta > 0$. (L’IA n’indique pas de valeur explicite pour $\delta$ dans la preuve originale, mais un raffinement à paraître, dû au professeur de mathématiques de Princeton Will Sawin, a montré que l’on peut prendre $\delta=0.014$.)

L'histoire du problème permet de comprendre pourquoi le résultat est surprenant. La meilleure borne inférieure connue était restée essentiellement inchangée depuis la construction originale d'Erdős en 1946. La meilleure borne supérieure, $O(n^{4/3})$, remonte à des travaux de Spencer, Szemerédi et Trotter en 1984 et, malgré des raffinements ultérieurs et des travaux structurels connexes de Székely, Katz et Silier, Pach, Raz et Solymosi, ainsi que d'autres, cette borne supérieure est restée essentiellement inchangée. Comme élément en faveur de la conjecture, Matoušek et Alon-Bucić-Sauermann ont étudié le problème avec des distances non euclidiennes dans le plan et ont prouvé que « la plupart » de ces distances non euclidiennes vérifient la conjecture dans un certain sens.

De façon surprenante, les ingrédients clés de la construction proviennent d'un domaine très différent des mathématiques, appelé théorie algébrique des nombres, qui étudie des notions comme la factorisation dans des extensions des entiers appelées corps de nombres algébriques.

À un niveau élevé, la preuve part d’une idée géométrique familière et la pousse dans une direction inattendue.

La borne inférieure originale d’Erdős peut se comprendre à travers les entiers de Gauss : des nombres de la forme $a+bi$, où $a$ et $b$ sont des entiers et $i$ est la racine carrée de $-1$. Les entiers de Gauss étendent les entiers ordinaires et, comme eux, possèdent des propriétés telles qu’une factorisation unique en nombres premiers. De telles extensions des entiers ordinaires ou des rationnels sont appelées corps de nombres algébriques. Le nouvel argument remplace les entiers de Gauss par des généralisations plus complexes issues de la théorie algébrique des nombres, dotées de symétries plus riches pouvant créer bien davantage de différences de longueur unitaire.

L’argument précis utilise des outils tels que les tours infinies de corps de classes et la théorie de Golod–Shafarevich pour montrer que les corps de nombres requis pour l’argument existent effectivement. Ces idées étaient bien connues des spécialistes de théorie algébrique des nombres, mais ce fut une grande surprise de constater que ces concepts ont des implications pour des questions géométriques dans le plan euclidien.

Ce résultat marque un moment important dans l’interaction entre l’IA et les mathématiques : un système d’IA a résolu de manière autonome un problème ouvert ancien au cœur d’un domaine actif. Il offre aussi un premier aperçu d’un nouveau type de collaboration entre l’IA et les mathématiciens humains. Dans ce cas, le travail complémentaire des mathématiciens externes dresse un tableau sensiblement plus riche que la seule solution originale.

Comme l’écrit Thomas Bloom dans la note complémentaire :

« Quand j’évalue l’importance et l’influence d’une preuve générée par l’IA, je me pose la question suivante : cela nous a-t-il appris quelque chose de nouveau sur le problème ? Comprenons-nous mieux la géométrie discrète maintenant ? Je pense que la réponse est oui, avec nuance : cela montre que les constructions issues de la théorie des nombres ont beaucoup plus à dire sur ce type de questions que nous ne le soupçonnions ; de plus, la théorie des nombres requise peut être très profonde. Il ne fait aucun doute que de nombreux spécialistes de théorie algébrique des nombres examineront de près d’autres problèmes ouverts de géométrie discrète dans les mois à venir. »

Le lien inattendu entre théorie algébrique des nombres et géométrie discrète révélé par la solution fait partie de ce qui rend ce résultat remarquable. Il ne se contente pas de trancher une conjecture précise, mais pourrait fournir aux mathématiciens un pont pour commencer à explorer d’autres problèmes liés.

Bloom évoque aussi une possibilité plus large :

« Les frontières de la connaissance sont très accidentées, et les mois et années à venir verront sans doute des succès similaires dans bien d’autres domaines des mathématiques, où des problèmes ouverts de longue date seront résolus par une IA révélant des connexions inattendues et poussant l’outillage technique existant jusqu’à sa limite. L’IA nous aide à explorer plus pleinement la cathédrale des mathématiques que nous avons bâtie au fil des siècles ; quelles autres merveilles encore invisibles attendent en coulisses ? »

Ce résultat offre un exemple prometteur : une IA apportant non seulement une solution, mais aussi une découverte mathématique dont la portée devient plus claire et plus riche grâce à la compréhension humaine ultérieure.

La leçon à retenir dépasse ce résultat particulier. Un meilleur raisonnement mathématique peut faire de l’IA un partenaire de recherche plus solide : quelque chose capable de maintenir des lignes de pensée difficiles, de relier des idées entre des domaines de connaissance éloignés, de faire émerger des pistes prometteuses que les experts n’auraient peut-être pas priorisées, et d’aider les chercheurs à progresser sur des problèmes qui seraient autrement trop complexes ou trop chronophages.

Ces capacités comptent au-delà des mathématiques. Si un modèle peut garder la cohérence d’un argument complexe, relier des idées entre des domaines de connaissance éloignés et produire un travail qui résiste à l’examen des experts, alors ce sont aussi des capacités utiles en biologie, en physique, en science des matériaux, en ingénierie et en médecine, et elles font partie de notre trajectoire à plus long terme vers une recherche davantage automatisée : des systèmes capables d’aider les scientifiques et les ingénieurs à explorer plus d’idées et à s’attaquer à des questions techniques plus difficiles.

L’IA est sur le point de commencer à jouer un rôle très sérieux dans les aspects créatifs de la recherche, et surtout dans la recherche en IA elle-même. Même si ces progrès ne sont pas inattendus, ils renforcent le sentiment d’urgence que nous éprouvons quant à la compréhension de cette prochaine phase du développement de l’IA, des défis liés à l’alignement de systèmes très intelligents et de l’avenir de la collaboration entre humains et IA.

Cet avenir dépend toujours du jugement humain. L’expertise devient plus précieuse, pas moins. L’IA peut aider à chercher, suggérer et vérifier. Ce sont les personnes qui choisissent les problèmes importants, interprètent les résultats et décident quelles questions poursuivre ensuite.