Problème des distances distinctes d'Erdős

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 n1 − o(1) distances distinctes. Le problème a été posé par Paul Erdős en 1946. En 2010, Larry Guth et Net Hawk Katz affirment 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 (en), Guth and Katz’s Solution of Erdős’s Distinct Distances Problem
  3. (en) l. Guth et N. H. Katz, « On the Erdős distinct distances problem on the plane », Annals of Mathematics,‎ (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]