next up previous
Next: Bibliography

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.


  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 $n^{2/3}$ and $n^{4/5}$ results dist08.pdf

  1. Erdos [4]. $n/\sqrt{\log n} \ge g_2(n) \ge \Omega(n^{0.5})$. erdos.pdf. These proofs are easy by today's 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.)

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

  10. Guth and Katz $g_2(n)$ $\ge$ $\Omega$ $(n/ \log n)$. See GK.

LOWER BOUND FOR $g_3$ and $g_d$.

We paraphrase 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 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 $g_d(n) \ge \Omega(n^{2/d - 1/d^2})$. In a subsequent 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)})$.

next up previous
Next: Bibliography
William Gasarch 2010-11-22