vignette|Les 6 distances distinctes entre sommets du dodécagone régulier. 6 est le nombre minimal de distances entre 12 points formant un polygone convexe, mais pas entre 12 points quelconques où il vaut 5. En géométrie discrète, le problème des distances distinctes d'Erdős concerne le nombre de distances distinctes possibles entre points distincts du plan euclidien, nombre au sujet duquel plusieurs conjectures ont été posées par Paul Erdős, en 1946, et en 1996. Elles concernent en particulier le minimum du nombre de distances distinctes. Erdős et Guy ont aussi étudié les sous-ensembles de présentant inversement le maximum de distances possibles.
Conjecture sur l'évaluation asymptotique de f(n) Dans son article de 1946, Erdős démontre l'encadrement pour une certaine constante . Le minorant est calculé par un raisonnement élémentaire; pour le majorant, Erdős considère les points à coordonnées entières où et sont compris entre 0 et ; toutes les longueurs obtenues sont alors racines carrées d'entiers qui s'expriment comme somme de deux carrés et il y a tels entiers (voir constante de Landau-Ramanujan), d'où le résultat. Erdős a conjecturé que ce majorant est une estimation assez précise de , c'est-à-dire qu'on a également (voir les notations de Landau).
En 2010, Larry Guth et Nets Hawk Katz annoncent avoir une solution Terence Tao, The Guth-Katz bound on the Erdős distance problem János Pach, Guth and Katz’s Solution of Erdős’s Distinct Distances Problem ; elle est publiée en 2015 par les Annals of Mathematics, mais démontre seulement la minoration .
Résultats successifs La minoration donné par Paul Erdős en 1946 a été successivement amélioré :
(Leo Moser, 1952), (Fan Chung, 1984), (Fan Chung, Endre Szemerédi, W. T. Trotter, 1992), (László Székely, 1993), (József Solymosi, C. D. Tóth, 2001), (Gábor Tardos, 2003), (Nets Katz, Gábor Tardos, 2004),
Cas d'un polygone convexe Dans son article de 1946, Erdős conjecture que si les points forment un polygone convexe alors le nombre minimal de distances distinctes est avec égalité lorsqu'ils forment un polygone régulier.
Valeur exacte de f(n) et configurations correspondantes Les valeurs de sont connues jusqu'à ( ) : +2345678910111213112233445556 vignette|Configuration de 12 points déterminant 5 distances distinctes; Erdős conjecture que c'est la seule.|gauche Jusqu'à , (le minimum est atteint entre autres par le n-gone régulier) ; pour , Erdős a trouvé trois autres configurations que l'ennéagone.
Pour , le dodécagone régulier n'est plus minimal ; est atteint par une configuration utilisant des nœuds du réseau hexagonal. vignette|Configuration de 13 points déterminant 6 distances distinctes, autre que le tridécagone régulier. Erdős définit comme le nombre maximal de points du plan définissant distances distinctes ; est en quelque sorte la réciproque de :
- , et si ,
- , et si .
Les valeurs de sont connues jusqu'à () : +12345635791213 Erdős conjecture que pour il existe des ensembles de nœuds du réseau hexagonal de taille .
Ensembles minimaux présentant toutes les distances possibles cadre|Règle de Golomb d'ordre 4 et de longueur 6.
Un exemple d'ensemble de points du plan présentant les distances possibles entre eux est formé des points de coordonnées ; il s'agit d'un cas particulier de règle de Golomb, ensemble de points de présentant les distances possibles. Il existe des règles de Golomb plus courtes que celle des puissances de 2 ; par exemple est plus courte que . La liste des longueurs des règles de Golomb les plus courtes est donnée par la : vignette|300x300px|Plus petit quadrilatère à coordonnées entières dont les longueurs de côtés et diagonales sont distinctes, illustration de . 2345678910136111725344455 Passant en dimension 2, Erdős et Guy ont posé en 1970 le problème d'évaluer les dimensions du plus petit carré de contenant points présentant les distances possibles.
La liste du nombre de points sur le côté d'un tel carré est donnée par la : 2345678910111213142345679101113151618 Un dénombrement élémentaire montre que , donc que .
Notes et références
Articles connexes
Graphe distance-unité
Catégorie:Géométrie discrète