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^[1][2] and almost proven by Larry Guth and Nets Katz in 2015.^[3][4][5]

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

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

for some constant ${\displaystyle c}$. The lower bound was given by an easy argument. The upper bound is given by a ${\displaystyle {\sqrt {n}}\times {\sqrt {n}}}$ square grid. For such a grid, there are ${\displaystyle 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) ${\displaystyle 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,^[6]
• g(n) = Ω(n^5/7) by Fan Chung in 1984,^[7]

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

Higher dimensions

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

See also

• Falconer's conjecture
• Erdős unit distance problem
• The Erdős Distance Problem