← La moisson des problèmes d'Erdős

Les distances unitaires : comment l'IA a eu Erdős

Le problème (1946)

Posez n points sur une feuille. Combien de paires peuvent se trouver à la même distance — disons à distance exactement 1 ? Avec n points on forme environ n²/2 paires, mais elles ne peuvent évidemment pas toutes être à distance 1. Erdős a montré en 1946 qu'une simple grille fait déjà très fort. Ci-contre, une grille de 49 points : on y compte 120 paires à la même distance (ici √5 : le point rouge la réalise avec 8 voisins — c'est le mouvement du cavalier aux échecs). En choisissant la distance la plus « populaire » d'une grande grille, Erdős obtenait un nombre de paires en n^{1+c/log log n} : à peine plus que n, mais un peu plus quand même. Et il conjecturait qu'on ne pouvait pas faire mieux — c'est la conjecture des distances unitaires, l'un des problèmes les plus connus de la géométrie discrète.

Ce que les humains savaient

Le point clé, c'est que ce problème de géométrie est de l'arithmétique déguisée : la distance populaire d'une grille est populaire parce que certains entiers s'écrivent comme somme de deux carrés d'un grand nombre de façons — un théorème sur les nombres premiers, pas sur les points. Dans l'autre sens, Spencer, Szemerédi et Trotter ont démontré en 1984 qu'on ne peut pas dépasser n^4/3 paires. Quarante ans d'efforts n'ont pas réussi à rapprocher les deux bornes : tout le monde, à la suite d'Erdős, pariait que la grille était optimale.

La solution de l'IA : pousser l'arithmétique à fond

En mai 2026, un modèle d'OpenAI a montré que la conjecture est fausse : il existe des configurations avec plus de n^1+δ paires à la même distance, pour un vrai exposant δ > 0 — un gain polynomial sur la grille. L'idée prolonge exactement celle d'Erdős, mais là où la grille exploite l'arithmétique des entiers ordinaires, la construction va la chercher dans des systèmes de nombres bien plus exotiques : des corps de nombres de très grand degré choisis pour être exceptionnellement « denses en coïncidences » (petit discriminant, beaucoup de premiers de petite norme — le critère utilisé, dit de Golod-Shafarevich, sert d'ordinaire à construire des tours infinies d'extensions). Dans ces systèmes, une même distance se répète énormément plus souvent que dans une grille. Le résultat a été relu par un comité de neuf mathématiciens de premier plan — dont Noga Alon, Tim Gowers et Melanie Matchett Wood — qui ont publié un article compagnon expliquant l'argument ; dans la foulée, Will Sawin (Princeton) a rendu l'exposant explicite : d'abord n^1,014, puis n^1,0318. La course qu'Erdős croyait finie est repartie.

Peut-on dessiner la configuration gagnante ?

Question naturelle : à quoi ressemble le « fuseau miracle » ? Réponse honnête : on ne peut pas le dessiner, et ce n'est pas une pirouette. La construction est une famille infinie dont l'avantage est asymptotique : elle ne dépasse la grille qu'à partir de tailles astronomiques, car les corps de nombres requis ont un degré énorme — les premiers membres intéressants de la famille comptent bien plus de points qu'il n'y a d'atomes dans l'univers. À toute échelle dessinable, les championnes restent les configurations à l'ancienne : pour 7 points, le record est de 12 paires, et le fameux fuseau de Moser en réalise déjà 11. C'est une leçon que la vulgarisation oublie souvent : un contre-exemple peut être parfaitement rigoureux et rester à jamais invisible — on démontre son existence, on ne le montrera jamais. (Des travaux cherchent depuis à « miniaturiser » des certificats explicites, mais on reste très loin d'une figure à épingler au mur.)

Pour aller plus loin

• L'annonce sur le blog de Gil Kalai — mai 2026, avec les liens vers la preuve et l'article compagnon.
• AI makes a major breakthrough in a math problem — phys.org, mai 2026.
• An explicit lower bound for the unit distance problem — Will Sawin (arXiv).
• Optimizing explicit unit-distance certificates — la « miniaturisation » des certificats (arXiv).