Monday, November 22, 2010

Erdos Distance Problem SOLVED!

(All papers referred to in this post can be accessed from my website on the Erdos Distance Problem.).

In 1946 Erdos raised the following question: Given n points in the plane how many distinct distances between points are you guaranteed? Let g(n) denote the number. How does g(n) grow? This problem is now called The Erdos distance Problem.

A while back I created a website of all(?) of the papers on this problem. Today I happily added one more paper to it which comes close to just about settling it. See also Tao's Blog on the recent result.

Julia Garibaldi, Alex Iosevich, and Steven Senger have a book due out in Jan 2011 entitled The Erdos Distance Problem. I proofread it for them so, without giving away the ending, I'll just say it is AWESOME.

I have seen it written that Erdos conjectured either g(n) &ge n/sqrt(log n) or g(n) &ge n1-&epsilon. These paper reference Erdos's 1946 paper. No such conjecture is there. I suspect Erdos did state the conjecture in talks.

I give a brief history:

  1. Erdos (1946) showed O(n/\sqrt(log n)) &ge g(n) &ge &Omega(n0.5). These proofs are easy by today's standards.
  2. Leo Moser (1952) showed g(n) &ge &Omega(n0.66...). (Actually n2/3.)
  3. Chung (1984) showed g(n) &ge &Omega(n0.7143...). (Actually n5/7.)
  4. Chung, Szemeredi, Trotter (1992) showed g(n) &ge &Omega(n 0.8/log n).
  5. Szekely (1993) showed g(n) &ge &Omega(n0.8).
  6. Solymosi and Toth (2004) showed g(n) &ge &Omega(n0.8571). (Actually n6/7.)
  7. On page 116 of Combinatorial Geometry and its Algorithmic Applications by Pach and Sharir there is a prediction about how far these techniques might go: A close inspection of the general Solymosi-Toth approach shows that, without any additional geometric idea, it can never lead to a lower bound greater than &Omega(n8/9). The exponent is 0.888... .
  8. Gabor Tardos (2003) showed g(n) &ge &Omega(n0.8634...). (Actually n(4e/(5e-1)) - &epsilon.)
  9. Nets Hawk Katz and Gabor Tardos (2004) showed g(n) &ge &Omega(n0.864...). Actually n((48-14e)/(55-16e)) - &epsilon).
  10. (ADDED LATER) Elekes and Sharir (2010) have a paper that sets up a framework which Guth and Katz used to get their result.
  11. (THE NEW RESULT) Guth and Katz (2010) showed g(n) &ge &Omega(n/log n).
Some thoughts
  1. There is a big gap between 1954 and 1984. I'd be curious why this is.
  2. I have seen it written that Erdos conjectured either g(n) &ge n/sqrt(log n) or g(n) &ge n1-&epsilon. These paper reference Erdos's 1946 paper. No such conjecture is there. I am sure that Erdos made the conjecture in talks.
  3. The paper by Szekely is a very good read and is elementary. Solymosi and Toth is still elementary but is getting harder. It is not clear when these papers cross the line from Could be presented to a bright high school student to Could not be.
  4. While there is a casual statement about needing new techniques this field did not go in the barriers-direction of formally proving certain techniques could not work.
  5. Did the new result use additional geometric ideas? Not sure yet- though I have emailed some people to ask.
  6. The first result by Erdos really is sqrt(n)-O(1), not \Omega(\sqrt(n)). The rest are asymptotic.
  7. If there are 289 points in the plane then there are at least 17 distinct distances. Are there more? I would be curious what happens for actual numbers like this. Exact results are likely very hard; however, some improvement may be possible.
  8. Gabor Tardos is Eva Tardos's brother. Nets Hawk Katz is not related to Jon Katz (Cryptographer and Blogger). (Nets Hawk Katz is a great stage name!) I do not know if Leo Moser and Robin Moser are related.


  1. Dear Bill
    Elekes Shamir paper seems missing

  2. Dear Gil-
    THANKS- I have inserted the paper into my website and also added it to the blog itself.


  3. Regarding #2, one paper by Erdos explicitly mentioning the conjecture is:

    P. Erdos, On some metric and combinatorial geometric problems, Discrete Mathematics, 60 (1986) 147-153.

    In the he abstract he calls it 'An old and probably very difficult conjecture'. He also offers $500 for a proof of it.

  4. What's going to happen to the book, which is probably already printed?

  5. doesn't sound SOLVED to me

  6. Not completely solved- OH, yes,
    that is correct. But very close.

    As for the author- he told me that he
    will try to get a line in about the problem
    before it goes to press.
    THe book will still be worthwhile as the proofs of the earlier results are easier and interesting.


  7. Isn't Erdos Distance currently at O(n/sqrt(log n))≥g(n)≥Ω(n/log n)?

  8. Erdos Distance Problem- YES, I
    should have said something like
    solved-within-a-log factor.

    I've even seen it stated as
    showing g(n) \ge n^{2-ep} for
    all ep>0. THAT version has been solved.

    Still very impressive and surprising.