Next: Bibliography

A Webpage on The Erdos Distance Problem

by William Gasarch

Erdos posed the following question: Let be the min number of distinct distances that you can get with points in . Try to find asymptotically. For example, if (the most studied case), this amounts to two questions: (1) How can you place points in the plane to minimize how many different distinct distances there are, and (2) Given any set of points in the plane, how many distinct distances are you guaranteed.

At this website I have hoped to gather all papers on this problem, with links. If you know of any I missed, let me know. I also include the citations. Some of them link to the original source.

SURVEYS AND WRITEUPS

1. Julia Garibaldi and Alex Iosevich have a survey in progress: erdoshs.pdf It will one day be a book. See Alex Iosevich's website for updates.
2. Alex Iosevich has a nice exposition of the Szemeredi-Trotter theorem sz.pdf (The articles title does not indicate that it has the Szemeredi-Trotter theorem, but it does.)
3. William Gasarch (oh, that's me!) has a writeup of the and results dist08.pdf

1. Erdos [4]. . erdos.pdf. These proofs are easy by today's standards. Try to do them yourself before looking at the paper.

2. Moser [7]. . moser.pdf (Actually )

3. Chung [2]. . chung.pdf (Actually )

4. Chung, Szemeredi, Trotter [3]. . CST.pdf

5. Szekely [11]. . szekely.pdf. This is a great paper that has a much easier proof then those in references 2,3,4 above.

6. Solymosi and Toth [5]. . soly.pdf Actually . This one is still elementary in that I think I can get through it. On page 116 of [8] says: 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 .

7. Tardos [12]. . tardos.pdf (Actually .) This one looks like it uses more advanced math.

8. Katz and Tardos [6]. . KT.pdf Actually This one looks like it uses more advanced math. (This is NOT Jon Katz, Crypto faculty at Univ of Maryland at College Park and Crypto-blogger.)

9. Elekes and Sharir ES. There are no new lower bounds on in this paper; however, Guth and Katz use their framework to obtain their result.

10. Guth and Katz . See GK.

LOWER BOUND FOR and .

We paraphrase page 101 of [8].

In three dimensions a recent result of Aronov, Pach, Sharir, Tardos [1] yields a lower bound of for any which is (APST.pdf for conference version or APSTpaper.pdf for paper version) This is still far from the best upper bound . A better lower bound of in a special case of homogeneous point sets has recently been proven by Solymosi and Vu [9]. Their analysis also applies to higher dimensional homogeneous point sets, and yields the bound . In a subsequent paper [10] the same authors tackled the general case and obtained a lower bound of .

Next: Bibliography
William Gasarch 2010-11-22