Problème des distances distinctes d'Erdős

En géométrie discrète, le problème des distances distinctes d'Erdős fait l'hypothèse qu'entre n points distincts sur une surface plane, il existe au moins n^{1 − o(1)} distances distinctes. Le problème a été posé par Paul Erdős en 1946. En 2010 dans un article en attente de vérification, Larry Guth et Net Hawk Katz affirment avoir une solution^[1],[2],[3].

La conjecture

Soit g(n) le nombre minimal de distances distinctes entre n points sur une surface plane. Dans son article de 1946, Erdős a démontré les estimés pour une certaine constante c. La borne inférieure est calculée de façon relativement simple, alors que la borne supérieure est donnée par une grille rectangulaire de dimensions (car il y a nombres sous n qui sont la somme de deux carrés, voir Constante de Landau-Ramanujan). Erdős a conjecturé que la borne supérieure est plus près de g(n), c'est-à-dire que g(n) = Ω(n^c) est vrai pour tout c < 1.

Résultats

La borne inférieure donnée par Paul Erdős en 1946 g(n) = Ω(n^1/2) a été successivement améliorée :

• g(n) = Ω(n^2/3) (Leo Moser, 1952),
• g(n) = Ω(n^5/7) (Fan Chung, 1984),
• g(n) = Ω(n^4/5/log n) (Fan Chung, Endre Szemerédi, W. T. Trotter, 1992),
• g(n) = Ω(n^4/5) (László Székely, 1993),
• g(n) = Ω(n^6/7) (József Solymosi, C. D. Tóth, 2001),
• g(n) = Ω(n^{(4e/(5e − 1)) − e}) (Gábor Tardos (en), 2003), and
• g(n) = Ω(n^{((48 − 14e)/(55 − 16e)) − e}) (Nets Hawk Katz, Gábor Tardos, 2004).

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Erdős distinct distances problem » (voir la liste des auteurs)

Bibliographie

• (en) P. Erdős, « On sets of distances of n points », dans American Mathematical Monthly, vol. 53, 1946, p. 248-250 [texte intégral] 
• (en) F. Chung, « The number of different distances determined by n points in the plane », dans Journal of Combinatorial Theory, (A), vol. 36, 1984, p. 342-354 [texte intégral [PDF], lien DOI] 

• Portail de la géométrie