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 $\sqrt{n-3/4}-1/2\leq g(n)\leq c n/\sqrt{\log n}$ 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 $\sqrt{n}\times\sqrt{n}$ (car il y a $O( n/\sqrt{\log n})$ 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)

1. ↑ (en) l. Guth et N. H. Katz, « On the Erdős distinct distance problem on the plane », dans Texte en accès libre sur arXiv : 1011.4105., 2010 
2. ↑ (en) Terence Tao, The Guth-Katz bound on the Erdős distance problem
3. ↑ (en) János Pach (en), Guth and Katz’s Solution of Erdős’s Distinct Distances Problem

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]