Erdős distinct distances problem

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[edit]

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

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; see Landau–Ramanujan constant. Erdős conjectured that the upper bound was closer to the true value of g(n), and specifically that holds for every c < 1.

Partial results[edit]

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

Higher dimensions[edit]

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)).

See also[edit]

References[edit]

External links[edit]