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 Modèle:Math points distincts sur une surface plane, il existe au moins Modèle:Math 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 solutionModèle:, ; elle est publiée en 2015 par les Annals of Mathematics.

La conjecture

Soit Modèle:Math le nombre minimal de distances distinctes entre Modèle:Math points sur une surface plane. Dans son article de 1946, Erdős a démontré l'encadrement $\sqrt{n-3/4}-1/2\le g(n)\le 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 de g(n), c'est-à-dire que $g(n)=\mathrm{\Omega }(n^c)$ est vrai pour tout Modèle:Math.

Résultats

La borne inférieure donnée par Paul Erdős en 1946 Modèle:Math a été successivement améliorée :

• Modèle:Math (Leo Moser, 1952),
• Modèle:Math (Fan Chung, 1984),
• Modèle:Math (Fan Chung, Endre Szemerédi, W. T. Trotter, 1992),
• Modèle:Math (László Székely, 1993),
• Modèle:Math (József Solymosi, C. D. Tóth, 2001),
• Modèle:Math (Gábor Tardos, 2003),
• Modèle:Math (Nets Katz, Gábor Tardos, 2004),
• Modèle:Math Modèle:Harv

Voir aussi

Articles connexes

• Modèle:Lien
• Graphe distance-unité

Bibliographie

• Modèle:Article
• Modèle:Article