Lorsqu’il entreprend de classifier les mathématiciens selon ce critère, il constate que la distinction n’est pas exclusive.
Si des mathématiciens reconnus comme Sir Michael Atiyah, Henri Poincaré ou Alexandre Grothendieck apparaissent clairement dans la première catégorie, les combinatoriciens en général, et Paul Erdös dont il va être question ci-dessous en particulier, sont plutôt classés dans la seconde. Sans discuter à l’infini de la pertinence de ce critère, on peut reconnaître que certains mathématiciens pourraient brillamment appartenir aux deux catégories.

Le problème des distances que nous allons évoquer et la conjecture [1] associée de Paul Erdös devraient davantage amuser les gens de la seconde catégorie. L’énoncé du problème est relativement simple et symbolique de toute une famille de problèmes de la discipline appelée combinatoire énumérative.

On reçoit un nombre $n$ de billes identiques et on nous demande de les disposer sur une table (sans qu’elles se touchent) en minimisant le nombre de distances différentes séparant deux billes.

Notons $d(n)$ le nombre minimal de distances différentes entre deux de ces $n$ billes.

Commençons avec trois points (la version mathématique des billes) $A$, $B$ et $C$ disposés comme suit :

Ces points définissent trois segments dont les longueurs $AC$, $AB$ et $BC$ sont distinctes. Mais si ces points forment un triangle équilatéral, comme ci-dessous,

alors les trois longueurs sont égales : $AB = AC = BC $. Dans cette nouvelle configuration, il n’y a qu’une distance. Le nombre minimal de distances pour trois points est donc $d(3) =1$.

Pour quatre points, on peut montrer qu’on ne peut pas avoir qu’une seule distance. La configuration suivante montre qu’on peut n’avoir que deux distances distinctes (qui correspondent au côté et à la diagonale) :

On a donc $d(4) = 2$ : quatre points distincts définissant toujours au moins deux distances distinctes et il existe une configuration qui n’en donne que deux.

On peut renouveler cette analyse avec $5$, $6$, $7$ points et trouver successivement $d(5)=2$, $d(6)=d(7)=3$. Toutefois, la situation se complexifie lorsque $n$ augmente. Devinez, par exemple, combien on obtient de distances distinctes avec les $10$ points suivants disposés régulièrement en « étoiles ». Commencez par les chercher avant d’aller regarder la description de ces distances proposée en note de bas de page [2].

Les mathématiciens n’ont pas trouvé (et n’ont pas d’espoir de trouver) une formule permettant de calculer $d(n)$. La conjecture de Erdös (1946) propose une réponse asymptotique à cette question en précisant l’ordre de grandeur du nombre de distances :

étant donnés $n$ points du plan, le nombre minimal de distances différentes entre deux de ces points est « presque de l’ordre de $n$ » lorsque $n$ tend vers $+\infty$.

Si la formulation adoptée ici peut sembler un peu vague, il n’en reste pas moins qu’un énoncé rigoureux est accessible pour un étudiant de premier cycle.

Nous allons esquisser quelques approches plus ou moins élaborées de cette conjecture jusqu’à l’article récent (2010) des mathématiciens Larry Guth et Nets Katz [3].

Une approche élémentaire : $\sqrt{n}$

Comme cela n’avait pas échappé à Paul Erdös, on peut obtenir une première minoration du nombre de distances différentes par un simple raisonnement « géométrique ».

Choisissons deux points parmi les $n$ points du plan et appelons-les $A_1$ et $A_2$. Traçons tous les cercles centrés en $A_1$ ou $A_2$ et passant par l’un des $n-2$ autres points $A_3$, ... $A_n$. Sur le dessin ci-dessous, on a représenté en rouge les cercles centrés en $A_1$ et en noir ceux centrés en $A_2$.

Notons $c_1$ le nombre de cercles ainsi obtenus centrés en $A_1$ (donc rouges) et $c_2$ le nombre de ceux centrés en $A_2$ (donc noirs) ; on suppose, quitte à changer les noms des deux points, que $c_1\geq c_2$. Comme deux cercles de centres différents ont au plus deux points d’intersection, il y a au plus $2c_1c_2$ points d’intersection sur la figure ($c_1$ choix pour le premier cercle, $c_2$ choix pour le deuxième et au plus $2$ choix pour l’intersection).

Or, par construction, chacun des $n-2$ points restants de notre ensemble de départ appartient à la fois à un cercle centré en $A_1$ et à un cercle centré en $A_2$ donc est un point d’intersection. On a donc $n-2\leq 2c_1c_2$ d’où l’on déduit $n-2\leq 2c_1^2$.

L’inégalité se réécrit alors $c_1\geq \sqrt{\frac{n-2}{2}}$ ce qui indique essentiellement que $c_1$ est au moins de l’ordre de $\sqrt{n}$. Mais $c_1$ est aussi le nombre de distances distinctes que l’on peut réaliser entre $A_1$ et l’un des $n-2$ autres points $A_3$, ... $A_n$. On a ainsi établi que le nombre de distances distinctes pour $n$ points était au moins de l’ordre de $\sqrt{n}$ (et ceci, indépendamment de la configuration de ces points).

Il existe de nombreuses autres preuves de ce « petit » résultat de minoration.

Une approche par la théorie des graphes : $n^{2/3}$

Un résultat un peu plus fort peut être obtenu, avec une dextérité certaine, en se ramenant à un résultat d’une théorie mathématique a priori indépendante, théorie des graphes.

Un graphe est un ensemble $S$ de sommets et un ensemble $A$ d’arêtes joignant deux sommets (il peut y en avoir plusieurs entre deux mêmes sommets comme il peut y avoir plusieurs routes entre deux villes). Voici par exemple deux dessins d’un même graphe à $5$ sommets et $8$ arêtes (on a juste déplacé des sommets et courbé des arêtes) :

On définit alors le nombre de croisements d’un graphe comme le nombre minimal (pour tous les dessins du graphe dans le plan) de croisements entre arêtes ; ci-dessus, il n’y a aucun croisement comme pour le graphe dont un dessin (mais pas celui qui réalise le minimum d’intersections) est

En revanche, il y a beaucoup de croisements pour le graphe dont un dessin est

Voici un théorème qui fournit une estimation du nombre de croisements.

Ainsi, on est ramené d’un problème sur un ensemble de points à un problème bien compris sur le nombre de croisements dans un graphe et l’on obtient ainsi une minoration de l’ordre de $n^{\frac23}$ (qui est donc meilleure que la précédente puisque $n^{\frac23}\geq n^{\frac12}=\sqrt{n}$. Par exemple, $1000000^{\frac23}= 10000$ alors que $100000^{\frac12}=1000$).

Le dernier résultat en date

Le dernier résultat concernant la conjecture d’Erdös a été annoncé On the Erdos distinct distance problem in the plane par Larry Guth et Nets Hawk Katz sur le site de prépublications ArXiV [5]. Il s’appuie aussi sur la réduction à un problème combinatoire classique (même si ce n’est pas le seul outil de ce bel article) : l’estimation du nombre d’incidence.

Initialement, le problème d’incidence est le suivant

étant donnés un ensemble $P$ de $n$ points et un ensemble $D$ de $m$ droites, combien existe-t-il au plus de couples formés d’un point de $P$ et d’une droite de $D$ tels que le point soit sur la droite ?

Ce problème est devenu un classique et le théorème de Szemeredi-Trotter (1983) fournit désormais une estimation optimale du nombre recherché [6].

Dans leur article, Larry Guth et Nets Hawk Katz se ramènent à un autre problème d’incidence déjà étudié par György Elekes et Micha Sharir dépendant de deux paramètres $n$ et $k$ :

étant données $n^2$ droites de l’espace (qui ne sont pas dans une position exceptionnelle comme par exemple des droites confondues), combien existe-t-il au plus de points qui appartiennent simultanément à $k$ droites ?

Ils résolvent alors ce problème utilisant tour à tour des outils géométriques [7] et topologiques [8] qui dépassent de loin le cadre d’une aussi courte présentation.

Conclusion

Le problème des distances distinctes s’énonce en termes facilement compréhensibles. Il n’en reste pas moins lié à d’autres problèmes (estimation du nombre de croisements dans un graphe, estimation du nombre d’incidence...) et demeure un sujet de recherche près de $60$ ans après sa mise en évidence par Erdös.

Si l’on repense à la discussion de Gowers évoquée en introduction, on peut constater que, loin d’être un passe-temps anecdotique, la résolution de problèmes est aussi un moyen pour les mathématiciens professionnels de faire avancer les connaissances et de développer des outils adaptés.

Bibliographie

• P. Erdös. On sets of distances of $n$ points. The American Mathematical Monthly, 53:248-250, 1946.
• L. Guth, N. H. Katz. On the Erdös distinct distance problem on the plane téléchargeable ici, ArXiV 2010.
• J. Garibaldi, A. Iosevich, S. Senger. The Erdös Distance Problem. Student Mathematical Library, AMS. 2010.