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 à une 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 en 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 un prix en argent pour la résolution de ce problème.

Aujourd’hui, nous présentons une percée sur le problème des distances unitaires. Depuis les travaux originaux d’Erdős, on croyait généralement que les constructions en « grille carrée » illustré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 de longue date, en fournissant une famille infinie d’exemples qui donnent 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 de contexte sur l’importance du résultat.

La façon dont le résultat a été obtenu est aussi 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-ci, 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 façon autonome par l’IA. Cela démontre aussi la profondeur du raisonnement que ces systèmes permettent désormais. 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 notable. 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 d’« étape importante pour les mathématiques de l’IA ». Selon l’éminent 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 accessible ici⁠(s'ouvre dans une nouvelle fenêtre). L’article complémentaire rédigé par d’éminents mathématiciens externes est accessible ici⁠(s'ouvre dans une nouvelle fenêtre). Vous pouvez trouver une version abrégée de la chaîne de pensée du modèle ici⁠(s'ouvre dans une nouvelle fenêtre).

Soit $u(n)$ le plus grand nombre possible de paires à distance unitaire parmi $n$ points dans le 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 meilleure construction connue auparavant, issue d’une grille carrée redimensionnée, s’avère en donner 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’atteignent 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 respectent la conjecture dans un certain sens.

Étonnamment, les ingrédients clés de la construction proviennent d’un tout autre domaine des mathématiques, appelé théorie algébrique des nombres, qui étudie des concepts comme la factorisation dans des extensions des entiers appelées corps de nombres algébriques.

À un niveau élevé, la preuve commence par 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 comme la 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 beaucoup plus de différences de longueur unitaire.

L’argument précis utilise des outils comme les tours infinies de corps de classes et la théorie de Golod–Shafarevich pour montrer que les corps de nombres requis par l’argument existent bel et bien. Ces idées étaient bien connues des spécialistes de la 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 façon autonome un problème ouvert de longue date 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-ci, le travail complémentaire des mathématiciens externes dresse un portrait nettement plus riche que la solution originale à elle seule.

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 genre de questions que nous 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 la théorie algébrique des nombres examineront de près d’autres problèmes ouverts en géométrie discrète dans les mois à venir. »

Le lien inattendu entre la théorie algébrique des nombres et la géométrie discrète révélé par la solution fait partie de ce qui rend le 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 connexes.

Bloom évoque aussi une possibilité plus large :

« Les frontières du savoir sont très accidentées, et il ne fait aucun doute que les mois et les années à venir verront des succès semblables 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 liens inattendus et poussant l’appareil technique existant à 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 qui apporte non seulement une solution, mais aussi une découverte mathématique dont l’importance 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 qui peut maintenir des lignes de pensée difficiles, relier des idées entre des domaines éloignés du savoir, faire ressortir des pistes prometteuses que les experts n’auraient peut-être pas priorisées, et aider les chercheurs à progresser sur des problèmes autrement trop complexes ou trop exigeants en temps.

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

L’IA est sur le point de 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 humain-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.