Le problème des distances unitaires d’Erdős

Une question simple à formuler

En géométrie discrète, le problème des distances unitaires d’Erdős pose une question étonnamment simple :

Parmi (n) points placés dans le plan euclidien, quel est le nombre maximal de paires de points séparées exactement par une distance égale à 1 ?

Autrement dit, si l’on place des points où l’on veut sur une feuille, combien de segments de longueur 1 peut‑on obtenir au maximum entre ces points ? Ce nombre maximal est généralement noté (U(n)).

La conjecture d’Erdős

Lorsque Paul Erdős a posé le problème en 1946, il a proposé une conjecture basée sur des configurations en réseau (grille carrée). Dans une grille d’environ (\sqrt{n} \times \sqrt{n}) points, de nombreuses paires horizontales et verticales sont à distance 1.

Ces constructions montrent que l’on peut obtenir un peu plus qu’un nombre linéaire de distances unitaires. Erdős a alors conjecturé que l’ordre de grandeur optimal est

n^(1 + o(1))

c’est‑à‑dire presque proportionnel à (n) lorsque (n) devient très grand .

La meilleure borne supérieure connue

Malgré des décennies de recherche, la borne générale la plus forte connue reste celle démontrée en 1984 par Joel Spencer, Endre Szemerédi et William Trotter :

U(n) = O(n^(4/3))

Cela signifie que, quelle que soit la disposition des points dans le plan, le nombre de paires à distance 1 ne peut pas dépasser une constante multipliée par (n^{4/3}) .

Cette borne reste bien plus grande que la croissance presque linéaire prédite par la conjecture d’Erdős.

L’état actuel du problème

Aujourd’hui, les mathématiciens connaissent seulement un encadrement entre deux bornes éloignées :

borne inférieure :  n^(1 + Ω(1 / log log n))
borne supérieure :  O(n^(4/3))
conjecture :        n^(1 + o(1))

La borne inférieure provient de constructions inspirées des réseaux de points, tandis que la borne supérieure découle de techniques avancées de géométrie combinatoire et de théorie des incidences .

Un problème toujours ouvert

Malgré l’attention de nombreux spécialistes pendant près de 80 ans, la conjecture complète d’Erdős n’a toujours pas été prouvée. Les chercheurs savent seulement que le nombre maximal de distances unitaires se situe quelque part entre ces deux estimations.

C’est précisément ce contraste entre une question très simple à énoncer et une difficulté extrême à résoudre qui fait du problème des distances unitaires l’un des classiques de la géométrie discrète moderne.