Problème des distances distinctes d'Erdős

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 ${\displaystyle {\sqrt {n-3/4}}-1/2\leq g(n)\leq cn/{\sqrt {\log n}}}$ pour une certaine constante ${\displaystyle 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 ${\displaystyle {\sqrt {n}}\times {\sqrt {n}}}$ (car il y a ${\displaystyle 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 ${\displaystyle g(n)=\Omega (n^{c})}$ est vrai pour tout c < 1.

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)