Les distances d’Erdös

Piste rouge Le 16 décembre 2014  - Ecrit par  Roger Mansuy Voir les commentaires (5)

Dans un joli petit texte, Timothy Gowers, médaille Fields 1998, classe les mathématiciens professionnels selon leur appétence et leur façon d’aborder les mathématiques :

  • d’un côté, ceux qui envisagent leur travail avant tout comme la construction de théories structurées, les theory-builders ;
  • de l’autre, ceux pour qui la compréhension d’un concept ou d’une réalité passe d’abord par la résolution de problèmes, les problem-solvers.

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 :

JPEG

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,

JPEG

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) :

JPEG

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].

JPEG

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.

Voici un énoncé plus précis.

Il s’agit de montrer qu’il existe une constante $C>0$ et un rang entier $N$ tel que si $n\geq N$, le nombre de distances différentes pour un ensemble de $n$ points est supérieur à $C \frac{n}{\sqrt{\ln n}}$.

Cette borne correspond à des points régulièrement espacés sur une grille carrée de côté $\sqrt{n}$ : Erdös s’est donc inspiré du calcul sur ce cas particulier pour énoncer la conjecture.

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$.

JPEG

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) :

JPEG

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

JPEG

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

JPEG

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

Théorème :
Le nombre de croisements d’un graphe à $s$ sommets, $a>4s$ arêtes et tel qu’il y a au plus $M$ arêtes entre deux sommets donnés est au moins de l’ordre de [\fraca^3Ms^2.]

On construit alors un graphe associé au problème des distances auquel on applique le théorème ci-dessus.

Nous pouvons revenir au problème des distances en construisant un graphe associé à un ensemble $S$ de $n$ points $A_1$, ..., $A_n$ réalisant $d$ distances distinctes :

  • les sommets sont ces points,
  • les arêtes sont les arcs des cercles centrés sur un point de $S$, passant par au moins $3$ points de $S$ et délimités par deux points de $S$.

Alors, on obtient pour ce graphe que [4]

  • le nombre de sommets est $n$ ;
  • le nombre d’arêtes est au plus $n(n-1)-2nd$ ;
  • le nombre de croisements est au plus $2(nd)^2$ ;
  • le nombre d’arêtes entre deux sommets est inférieur à $2d$.

Le théorème admis sur les graphes donne alors (en notant $\gg$ la relation « être au moins de l’ordre ») [(nd)^2\gg c\gg \fraca^3Ms^2\gg \fracn^62dn^2,]
soit $d\gg n^{\frac23}$.

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.
Post-scriptum :

J’ai eu la chance de pouvoir présenter ces résultats et quelques autres lors d’un exposé du séminaire Mathematic Park pour étudiants des premiers cycles. La captation de cet exposé est disponible à l’adresse suivante (il y a un problème de son pendant les premières minutes) alors que les transparents qui servent de support sont disponibles sur la page de l’institut.

Je tiens à remercier l’éditeur Jérôme Buzzi et les relecteurs du site, Aziz El Kacimi, vic20, nakhil et Simon Iosti pour leurs conseils et leur aide à rendre l’article plus accessible dans le cadre Images des Mathématiques.

Article édité par Jérôme Buzzi

Notes

[1Une conjecture est un résultat intuité, non démontré et soumis à la sagacité de la communauté mathématique. Le « théorème » de Fermat était de fait une conjecture jusqu’aux travaux de Andrew Wiles. Parmi les conjectures les plus médiatiques, on trouve la conjecture de Goldbach, « l’hypothèse » de Riemann ou la comparaison des classes de complexité algorithmique P et NP.

[2Voici une illustration de ces $7$ distances JPEG

[3Ils annoncent que le nombre de distances distinctes est au moins de l’ordre de $\frac{n}{\ln n}$ alors que la conjecture d’Erdös prévoit $\frac{n}{\sqrt{\ln n}}$. On peut comparer ce résultat avec la borne de la conjecture d’Erdös en comparant les ordres de grandeur
\[\begin{array}{|c||r|r|r|r|}\hline n & 10^2 & 10^3 & 10^6 & 10^9 \\\hline \frac{n}{\ln n} & 21.71 & 144.76 & 72382.41 & 48254942.43\\\hline \frac{n}{\sqrt{\ln n}} & 46.60 & 380.48 & 269039.80 & 219670076.33\\ \hline \end{array} \]
Rappelons que la fonction logarithme $\ln$ a une croissance lente puisque $\ln n$ est approximativement le nombre de chiffres de l’écriture de $n$ (c’est, à un facteur près, le logarithme décimal) ; $\sqrt{\ln n}$ est donc la racine carrée du nombre du chiffres de $n$ (ce qui se calcule rapidement avec une simple calculatrice, contrairement à $d(n)$). Ceci explique l’écart entre les deux dernières lignes du tableau (la borne de la conjecture et celle établie par Guth et Katz).

[4Ce dénombrement demande quelques efforts pour le non initié.

[5Le premier manuscrit a été soumis en 2010 puis révisé en 2011 ; il est depuis en cours d’examen par le prestigieux journal Annals of Maths mais a déjà été cité, repris voire complété par de nombreux chercheurs.

[6On peut remarquer qu’une des preuves de ce résultat due à Szekely repose elle aussi sur l’estimation du nombre de croisements dans un graphe mentionné ci-dessus.

[7Essentiellement, des études de surfaces réglées.

[8Essentiellement une version discrète du célèbre théorème du sandwich.

Partager cet article

Pour citer cet article :

Roger Mansuy — «Les distances d’Erdös» — Images des Mathématiques, CNRS, 2014

Commentaire sur l'article

  • Les distances d’Erdös

    le 16 décembre 2014 à 15:20, par amic

    On pourrait réduire à 6 le nombre de distances dans la figure à 10 points : le segment tracé le plus à gauche dans l’image qui sert de logo peut être arbitrairement fixé comme étant de même longueur que le petit horizontal.

    Et sinon, j’ai relevé une typo : 1000000 et 100000…

    Répondre à ce message
    • Les distances d’Erdös

      le 16 décembre 2014 à 20:24, par Roger Mansuy

      Merci pour la typo sur les puissances de 10. En revanche, d’après la construction géométrique du logo, il y a bien 7 distances différentes.

      Répondre à ce message
  • Les distances d’Erdös

    le 16 décembre 2014 à 22:05, par amic

    Oui, sur la construction géométrique il y a 7 distances, mais il suffirait de réduire un peu la taille du pentagone du milieu pour faire que deux distances parmi ces 7 soient égales.

    Répondre à ce message
  • Les distances d’Erdös

    le 12 décembre 2015 à 23:35, par Formimadle

    Pour la figure à dix points, ne vaut-il mieux pas construire un cercle de rayon x, avec un point pour centre, placer les 9 autres points autour de ce dernier, de sorte qu’ils forment un ennéagone, avec pour longueur de chaque côté x.
    Ainsi, nous avons une seule distance, x (celle du rayon et des côtés) à laquelle s’ajoutent 3 distances, celles des différents points composant l’ennéagone, j’en compte 4, ce qui fait 5 distances au total et non 6 ! Ceci à été fait de tête donc je me trompe peut-être mais c’est à vérifier.
    L’on peut aussi remarquer que cette technique, celle de former un cercle de rayon x autour duquel s’organise en polygone régulier le reste des points est très avantageux pour les nombres de points pairs, pour les nombres impairs, simplement créer un polygone régulier. Outre cette méthode de construction, je remarque que ;
    d2=1
    d3=1
    d4=2
    d5=2
    d6=3
    d7=3
    d8=4
    d9=4
    d10=5
    d11=5
    d12=6
    d13=6
    .
    .
    .
    d50=25
    d51=25
    d200=100
    d201=100

    Si les types de constructions cités précédemment sont les plus simples, celles qui minimalisent le nombre de distance, alors nous obtenons ces chiffres et pouvons dire que le nombre de distances minimales sera égale au nombre de points divisés par 2, et si cela donne un chiffre à virgule, on arrondie à l’entier inférieur.

    Répondre à ce message
  • Les distances d’Erdös

    le 13 décembre 2015 à 01:32, par Formimadle

    je m’excuse de ce double-post mais il me reste deux choses à clarifier ; le fait que pour la construction du cercle et du polygone régulier (cas où le nombre de point est pair), il est impossible que le rayon x soit égal aux côtés du polygone, donc je corrige cela (pour 6, on trace un cercle puis un pentagone, il n’y aura pas de triangles équilatéraux qui interviendront). Je rajoute aussi le fait que pour les nombres pairs, la formule est N/2, et pour les nombres impairs, elle est de (N/2)-0,5. Un point oublié est celui de 1, en effet d(1)=0 puisqu’il n’y a pas de distances.

    Dans ces commentaires, aucun démonstration n’a été réalisée, j’espère pouvoir écrire un article, avec démonstration si mes résultats sont cohérents et répondent donc comme solution à ce problème.

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM