Kalpana Kalpana (Editor)

Erdős distinct distances problem

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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

Contents

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

n − 3 / 4 − 1 / 2 ≤ g ( n ) ≤ c n / log ⁡ n

for some constant c . The lower bound was given by an easy argument. The upper bound is given by a n × n square grid. For such a grid, there are O ( n / 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 g ( n ) = Ω ( n c ) holds for every c < 1.

Partial results

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

  • g(n) = Ω(n2/3) (Moser 1952)
  • g(n) = Ω(n5/7) (Chung 1984)
  • g(n) = Ω(n4/5/log n) (Chung, Szemerédi & Trotter 1992)
  • g(n) = Ω(n4/5) (Székely 1993)
  • g(n) = Ω(n6/7) (Solymosi & Tóth 2001)
  • g(n) = Ω(n(4e/(5e − 1)) − ɛ) (Tardos 2003)
  • g(n) = Ω(n((48 − 14e)/(55 − 16e)) − ɛ) (Katz & Tardos 2004)
  • g(n) = Ω(n/log n) (Guth & Katz 2015)

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

    References

    Erdős distinct distances problem Wikipedia
    (Text) CC BY-SA


    Similar Topics