A WebPage on The Erdos Distance Problem

by William Gasarch

Erdos posed the following question: Let $g_d(n)$ be the min number of distinct distances that you can get with $n$ points in $R^d$. Try to find $g_d(n)$ asymptotically. For example, if $d=2$ (the most studied case), this amounts to two questions: (1) How can you place $n$ points in the plane to minimize how many different distinct distances there are, and (2) Given any set of $n$ 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 Szemereti-Trotter theorem, but it does.)
3. William Gasarch (oh, thats me!) has a writeup of the $n^{2/3}$ and $n^{4/5}$ results dist08.pdf

LOWER BOUNDS ON $g_2$ AND THE ONE UPPER BOUND In order of publication.

1. Erdos [4]. $n/\sqrt{\log n} \ge g_2(n) \ge \Omega(n^{0.5})$. erdos.pdf. These proofs are easy by todays standards. Try to do them yourself before looking at the paper.

2. Moser [7]. $g_2(n) \ge \Omega(n^{0.66\ldots})$. moser.pdf (Actually $\Omega(n^{2/3})$)

3. Chung [2]. $g_2(n) \ge \Omega(n^{0.7143\ldots})$. chung.pdf (Actually $\Omega(n^{5/7})$)

4. Chung, Szemeredi, Trotter [3]. $g_2(n) \ge \Omega(n^{0.8}/\log n)$. CST.pdf

5. Szekely [11]. $g_2(n) \ge \Omega(n^{0.8})$. 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]. $g_2(n) \ge \Omega(n^{0.8571})$. soly.pdf Actually $\Omega(n^{6/7})$. 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 $\Omega(n^{8/9})$.

7. Tardos [12]. $g_2(n) \ge \Omega(n^{0.8634\ldots})$. tardos.pdf (Actually $\Omega(n^{(4e/(5e-1)) - \epsilon})$.) This one looks like it uses more advanced math.

8. Katz and Tardos [6]. $g_2(n) \ge \Omega(n^{0.864\ldots})$. KT.pdf Actually $\Omega(n^{((48-14e)/(55-16e)) - \epsilon})$ 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.)

LOWER BOUND FOR $g_3$ and $g_d$.

We paragraphse page 101 of [8].

In three dimensions a recent result of Aronov, Pach, Sharir, Tardos [1] yields a lower bound of $g_3(n) \ge \Omega(n^{77/141 - \epsilon})$ for any $\epsilon>0$ which is $\Omega(n^{0.546})$ (APST.pdf for conference version or APSTpaper.pdf for paper version) This is still far from the best upper bound $g_3(n) \le O(n^{2/3})$. A better lower bound of $\Omega(n^{0.5794})$ in a special case of homogenous point sets has recently been proven by Solymosi and Vu [9]. Their analysis also applies to higher dimensional homogenous point sets, and yields the bound $g_d(n) \ge \Omega(n^{2/d - 1/d^2})$. In a subsequenet paper [10] the same authors tackled the general case and obtained a lower bound of $g_d(n) \ge \Omega(n^{2/d - 2/d(d+2)})$.