Problème des distances distinctes d'Erdős : La conjecture, Résultats, Notes et références, Voir aussi Wikipédia, l'encyclopédie libre

Problème des distances distinctes d'Erdős

En géométrie discrète, le problème des distances distinctes d'Erdős est l'énoncé 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, Larry Guth et Nets Hawk Katz annoncent avoir une solution^[1]^,^[2] ; elle est publiée en 2015 par les Annals of Mathematics^[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é l'encadrement ${\sqrt {n-3/4}}-1/2\leq g(n)\leq cn/{\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 une estimation assez précise^[4] de g(n), c'est-à-dire que $g(n)=\Omega (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, 2003),
g(n) = Ω(n^{((48 − 14e)/(55 − 16e)) − e}) (Nets Katz, Gábor Tardos, 2004),
g(n) = Ω(n/log n) (Guth et Katz 2015)

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

↑ (en) Terence Tao, The Guth-Katz bound on the Erdős distance problem
↑ (en) János Pach, Guth and Katz’s Solution of Erdős’s Distinct Distances Problem
↑ (en) Larry Guth et Nets H. Katz, « On the Erdős distinct distances problem on the plane », Annals of Mathematics,‎ 2015, p. 155–190 (DOI 10.4007/annals.2015.181.1.2, lire en ligne)
↑ Voir l'article comparaison asymptotique pour l'utilisation des notations $O(f(n))$ et $\Omega (f(n))$ .

Voir aussi

Bibliographie

(en) P. Erdős, « On sets of distances of n points », American Mathematical Monthly, vol. 53,‎ 1946, p. 248-250 (lire en ligne)
(en) F. Chung, « The number of different distances determined by n points in the plane », Journal of Combinatorial Theory, (A), vol. 36,‎ 1984, p. 342-354 (DOI 10.1016/0097-3165(84)90041-4, lire en ligne [PDF])