Problème des distances distinctes d'Erdős

Un article de Wikipédia, l'encyclopédie libre.

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 n1 − 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[modifier | modifier le code]

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 pour une certaine constante . 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 une estimation assez précise[4] de g(n), c'est-à-dire que est vrai pour tout c < 1.

Résultats[modifier | modifier le code]

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

Notes et références[modifier | modifier le code]

(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) Terence Tao, The Guth-Katz bound on the Erdős distance problem
  2. (en) János Pach, Guth and Katz’s Solution of Erdős’s Distinct Distances Problem
  3. (en) Larry Guth et Nets H. Katz, « On the Erdős distinct distances problem on the plane », Annals of Mathematics,‎ , p. 155–190 (DOI 10.4007/annals.2015.181.1.2, lire en ligne)
  4. Voir l'article comparaison asymptotique pour l'utilisation des notations et .

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]