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] The current best result was achieved by Larry Guth and Nets Katz in 2015.^[3]^[4]^[5]

Erdős considered this problem as his "most striking contribution to geometry".^[6]

The conjecture

Place n distinct points in a plane. There are ${\tfrac {1}{2}}(n^{2}-n)$ distinct pairs between them. Of these pairs, some have the same length, and some have different lengths. The maximum number of different lengths achievable is ${\tfrac {1}{2}}(n^{2}-n)$ , using the following points: $(0,0),(0,1),(0,3),(0,7),\dots ,(0,2^{n-1}-1)$ .

The minimum number of different lengths achievable is more difficult to find. Let this number be $g (n)$ . Equivalently, it is 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$ . In big-O notation, $g\leq O(n/{\sqrt {\log n}})$ .

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 $O(n/{\sqrt {\log n}})$ is very close to being tight: $g(n)=\Omega (n^{c})$ holds for every $c < 1$ , using big Omega notation. More succinctly, $g(n)\geq \Omega _{*}(n)$ .

He further conjectured that the upper bound is exactly tight: $g(n)=\Theta (n/{\sqrt {\log n}})$ , and offered a prize of $500 for either proving or disproving the conjecture.^[7]

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,^[8]
$g (n) = Ω (n 5/7)$ by Fan Chung in 1984,^[9]

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

Variants

Restricted subsets

Instead of allowing the n distinct points to be placed anywhere in a plane, we can additionally require the points to satisfy constraints. In general, the more stringent the constraints are, the larger $g$ gets.

If we require the points to fall on a single line, then $g_{\text{line}}(n)=n-1$ by setting the points equally spaced. If we require the points to fall on a single circle, then $g_{\text{circle}}(n)=\lfloor n/2\rfloor$ by setting the points equally spaced around the circle. More generally, if we require the points to form a convex polygon, then $g_{\text{convex}}(n)=\lfloor n/2\rfloor$ . The same, if we require the points to form a strictly convex polygon.^[15]^[16]

If we require the points to be in general position, meaning no 3 points are collinear and no 4 points are cocircular, then it is an open problem. Currently the best result is $g_{\text{gen}}(n)\geq \Omega (n)$ and $g_{\text{gen}}\leq n2^{O({\sqrt {\log n}})}$ .^[17]

If we require the points to be in general ,position and no 4 points form a parallelogram, then it is an open problem. Currently the best result is $g_{\text{para}}(n)\geq \Omega (n)$ and $g_{\text{para}}\leq O(n^{2}/{\sqrt {\log n}})$ .^[18]^[17]

See Section 3 of ^[19] for more problems and results of the kind.

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.^[20]

In the other direction, it's known currently that $g_{3}(n)\geq \Omega _{*}(n^{3/5})$ , by applying the recursion relation of ^[21] to the result $g_{2}(n)\geq \Omega _{*}(n)$ of (Guth & Katz 2015).^[19]

Generic norms

The same question can be asked for any normed space. Given a norm $\|\cdot \|$ , define $g_{\|\cdot \|}(n)$ accordingly. The problem is solved in the generic case. Specifically, given any integer $d\geq 2$ , for almost all norms $\|\cdot \|$ , $g_{\|\cdot \|}(n)=(1-o(1))n$ That is, the set of norms that violate this condition is meagre in the set of all norms of $\mathbb {R} ^{d}$ , regarded as a metric space, metrized by the Hausdorff distance between the norm-unit balls.^[19]^[22]