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 Guth & Katz (2015).

The conjecture

In what follows let g(n) denote the minimal number of distinct distances between n 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(n), and specifically that (using big Omega notation) 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 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., . Solymosi & Vu (2008) obtained the lower bound .

See also

References

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.