# Erdős distinct distances problem

In discrete geometry, the Erdős distinct distances problem states that between n distinct points on a plane there are at least n1 − o(1) distinct distances. It was posed by Paul Erdős in 1946 and proven by Guth & Katz (2015).

## The conjecture

In what follows let g(n) denote the minimal number of distinct distances between n points in the plane. 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; see Landau–Ramanujan constant. Erdős conjectured that the upper bound was closer to the true value of g(n), and specifically that ${\displaystyle g(n)=\Omega (n^{c})}$ holds for every c < 1.

## Partial results

Paul Erdős' 1946 lower bound of g(n) = Ω(n1/2) was successively improved to:

## Higher dimensions

Erdős also considered the higher-dimensional variant of the problem: for d≥3 let gd(n) denote the minimal possible number of distinct distances among n point in the d-dimensional Euclidean space. He proved that gd(n) = Ω(n1/d) and gd(n) = O(n2/d) and conjectured that the upper bound is in fact sharp, i.e., gd(n) = Θ(n2/d) . Solymosi & Vu (2008) obtained the lower bound gd(n) = Ω(n2/d - 2/d(d+2)).