title: Problème des distances distinctes d'Erdős
text: # 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 n points distincts sur une surface plane, il existe au moins n 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^,$ ; elle est publiée en 2015 par les Annals of Mathematics.
  
  ## La conjecture
  
  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 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)=\Omega (n^{c})$ est vrai pour tout c < 1.
  
  ## Résultats
  
  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)
  