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

- 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.
- 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.)
- William Gasarch (oh, that's me!) has a writeup of the and results dist08.pdf

- Erdos [4].
.
erdos.pdf.
These proofs are easy by today's standards.
Try to do them yourself before looking at the paper.
- Moser [7].
.
moser.pdf
(Actually
)
- Chung [2].
.
chung.pdf
(Actually
)
- Chung, Szemeredi, Trotter [3].
.
CST.pdf
- Szekely [11].
.
szekely.pdf.
This is a great paper that has a much easier proof
then those in references 2,3,4 above.
- 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 .* - Tardos [12].
.
tardos.pdf
(Actually
.)
This one looks like it uses more advanced math.
- 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.)
- 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.
- 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
.