Erdős distinct distances problem

Template:Short description 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 Template:Math denote the minimal number of distinct distances between Template:Math 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\le g(n)\le 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)=\mathrm{\Omega }(n^c)$ holds for every Template:Math.

Partial results

Paul Erdős' 1946 lower bound of Template:Math was successively improved to:

• Template:Math by Leo Moser in 1952,
• Template:Math by Fan Chung in 1984,

• Template:Math by Fan Chung, Endre Szemerédi, and William T. Trotter in 1992,
• Template:Math by László A. Székely in 1993,
• Template:Math by József Solymosi and Csaba D. Tóth in 2001,
• Template:Math by Gábor Tardos in 2003,
• Template:Math by Nets Katz and Gábor Tardos in 2004,
• Template:Math by Larry Guth and Nets Katz in 2015.

Higher dimensions

Erdős also considered the higher-dimensional variant of the problem: for $d\ge 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)=\mathrm{\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)=\mathrm{\Theta }(n^{2/d})$. József Solymosi and Van H. Vu obtained the lower bound $g_d(n)=\mathrm{\Omega }(n^{2/d-2/d(d+2)})$ in 2008.

See also

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

External links

• William Gasarch's page on the problem