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 n^{1-&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:
- Erdos (1946) showed O(n/\sqrt(log n)) &ge g(n) &ge &Omega(n^{0.5}). These proofs are easy by today's standards.
- Leo Moser (1952) showed g(n) &ge &Omega(n^{0.66...}). (Actually n^{2/3}.)
- Chung (1984) showed g(n) &ge &Omega(n^{0.7143...}). (Actually n^{5/7}.)
- Chung, Szemeredi, Trotter (1992) showed g(n) &ge &Omega(n ^{0.8}/log n).
- Szekely (1993) showed g(n) &ge &Omega(n^{0.8}).
- Solymosi and Toth (2004) showed g(n) &ge &Omega(n^{0.8571}). (Actually n^{6/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(n^{8/9}). The exponent is 0.888... .
- Gabor Tardos (2003) showed g(n) &ge &Omega(n^{0.8634...}). (Actually n^{(4e/(5e-1)) - &epsilon}.)
- Nets Hawk Katz and Gabor Tardos (2004) showed g(n) &ge &Omega(n^{0.864...}). Actually n^{((48-14e)/(55-16e)) - &epsilon)}.
- (ADDED LATER) Elekes and Sharir (2010) have a paper that sets up a framework which Guth and Katz used to get their result.
- (THE NEW RESULT) Guth and Katz (2010) showed g(n) &ge &Omega(n/log n).
- There is a big gap between 1954 and 1984. I'd be curious why this is.
- I have seen it written that Erdos conjectured either g(n) &ge n/sqrt(log n) or g(n) &ge n^{1-&epsilon}. These paper reference Erdos's 1946 paper. No such conjecture is there. I am sure that Erdos made the conjecture in talks.
- 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.
- 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.
- Did the new result use additional geometric ideas? Not sure yet- though I have emailed some people to ask.
- The first result by Erdos really is sqrt(n)-O(1), not \Omega(\sqrt(n)). The rest are asymptotic.
- 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.
- 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.
Dear Bill
ReplyDelete"all(?)"
Elekes Shamir paper seems missing
http://front.math.ucdavis.edu/1005.0982
Dear Gil-
ReplyDeleteTHANKS- I have inserted the paper into my website and also added it to the blog itself.
GASARCH
Regarding #2, one paper by Erdos explicitly mentioning the conjecture is:
ReplyDeleteP. 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.
What's going to happen to the book, which is probably already printed?
ReplyDeletedoesn't sound SOLVED to me
ReplyDeleteNot completely solved- OH, yes,
ReplyDeletethat 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.
GASARCH
Isn't Erdos Distance currently at O(n/sqrt(log n))≥g(n)≥Ω(n/log n)?
ReplyDeleteErdos Distance Problem- YES, I
ReplyDeleteshould 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.