Erdős distinct distances problem
# Erdős distinct distances problem

In discrete geometry, the Erdős distinct distances problem states that every set of points in the plane has a nearly-linear number of distinct distances. It was posed by Paul Erdős in 1946 and almost proven by Larry Guth and Nets Katz in 2015.

## The conjecture

In what follows let g(n) denote the minimal number of distinct distances between n points in the plane, or equivalently the smallest possible cardinality of their distance set. In his 1946 paper, Erdős proved the estimates

    ${\sqrt {n-3/4}}-1/2\leq g(n)\leq cn/{\sqrt {\log n}}$

for some constant $c$. The lower bound was given by an easy argument. The upper bound is given by a ${\sqrt {n}}\times {\sqrt {n}}$ square grid. For such a grid, there are $O(n/{\sqrt {\log n}})$ numbers below n which are sums of two squares, expressed in big O notation; see Landau–Ramanujan constant. Erdős conjectured that the upper bound was closer to the true value of g(n), and specifically that (using big Omega notation) $g(n)=\Omega (n^{c})$ holds for every c < 1.

## Partial results

Paul Erdős' 1946 lower bound of g(n) = $Ω(n^{1/2})$ was successively improved to:

* g(n) = $Ω(n^{2/3})$ by Leo Moser in 1952,
* g(n) = $Ω(n^{5/7})$ by Fan Chung in 1984,
* g(n) = $Ω(n^{4/5}/log$ n) by Fan Chung, Endre Szemerédi, and William T. Trotter in 1992,
* g(n) = $Ω(n^{4/5})$ by László A. Székely in 1993,
* g(n) = $Ω(n^{6/7})$ by József Solymosi and Csaba D. Tóth in 2001,
* g(n) = $Ω(n^{(4e/(5e−1))−ɛ})$ by Gábor Tardos in 2003,
* g(n) = $Ω(n^{((48−14e)/(55−16e))−ɛ})$ by Nets Katz and Gábor Tardos in 2004,
* g(n) = Ω(n/log n) by Larry Guth and Nets Katz in 2015.

## Higher dimensions

Erdős also considered the higher-dimensional variant of the problem: for $d\geq 3$ let $g_{d}(n)$ denote the minimal possible number of distinct distances among $n$ points in $d$-dimensional Euclidean space. He proved that $g_{d}(n)=\Omega (n^{1/d})$ and $g_{d}(n)=O(n^{2/d})$ and conjectured that the upper bound is in fact sharp, i.e., $g_{d}(n)=\Theta (n^{2/d})$. József Solymosi and Van H. Vu obtained the lower bound $g_{d}(n)=\Omega (n^{2/d-2/d(d+2)})$ in 2008.

