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 and almost proven by.

The conjecture

In what follows let denote the minimal number of distinct distances between points in the plane, or equivalently the smallest possible cardinality of their distance set. In his 1946 paper, Erdős proved the estimates
for some constant. The lower bound was given by an easy argument. The upper bound is given by a square grid. For such a grid, there are 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, and specifically that holds for every.

Partial results

Paul Erdős' 1946 lower bound of was successively improved to:
Erdős also considered the higher-dimensional variant of the problem: for let denote the minimal possible number of distinct distances among points in -dimensional Euclidean space. He proved that and and conjectured that the upper bound is in fact sharp, i.e., . obtained the lower bound .