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, dans un article en attente de vérification (mais considéré comme correct par des mathématiciens tels que Terence Tao), Larry Guth et Net Hawk Katz affirment avoir une solution[1],[2],[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 \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 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[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) l. Guth et N. H. Katz, « On the Erdős distinct distance problem on the plane », arxiv,‎ 2010 Texte en accès libre sur arXiv : 1011.4105.
  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
  4. Voir l'article comparaison asymptotique pour l'utilisation des notations O(f(n)) et \Omega(f(n)).

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]