Erdős distinct distances problem

Short description: Problem in discrete geometry

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. The current best result was achieved by Larry Guth and Nets Katz in 2015.

Erdős considered this problem as his "most striking contribution to geometry".

The conjecture

Place n distinct points in a plane. There are $\frac{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 $\frac{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\le g(n)\le cn/\sqrt{\log n}$

for some constant $c$. In big-O notation, $g\le 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)=\mathrm{\Omega }(n^c)$ holds for every c < 1, using big Omega notation. More succinctly, $g(n)\ge {\mathrm{\Omega }}_{*}(n)$.

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

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.

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.

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)\ge \mathrm{\Omega }(n)$ and $g_{\text{gen}}\le n{2}^{O(\sqrt{\log n})}$.

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)\ge \mathrm{\Omega }(n)$ and $g_{\text{para}}\le O(n^2/\sqrt{\log n})$.

See Section 3 of for more problems and results of the kind.

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.

In the other direction, it's known currently that $g_3(n)\ge {\mathrm{\Omega }}_{*}(n^{3/5})$, by applying the recursion relation of to the result $g_2(n)\ge {\mathrm{\Omega }}_{*}(n)$ of (Guth Katz).

Generic norms

The same question can be asked for any normed space. Given a norm $\Vert \cdot \Vert$, define $g_{\Vert \cdot \Vert }(n)$ accordingly. The problem is solved in the generic case. Specifically, given any integer $d\ge 2$, for almost all norms $\Vert \cdot \Vert$,$$g_{\Vert \cdot \Vert }(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{ℝ}}^d$, regarded as a metric space, metrized by the Hausdorff distance between the norm-unit balls.

See also

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

Further reading

• Sheffer, Adam (2018-07-02). "Distinct Distances: Open Problems and Current Bounds". arXiv:1406.1949v3 [math.CO].
• Garibaldi, Julia; Iosevich, Alex; Senger, Steven (2011), The Erdős Distance Problem, Student Mathematical Library, 56, Providence, RI: American Mathematical Society, ISBN 978-0-8218-5281-1 

External links

• William Gasarch's page on the problem