The Erdos Distance Problem}

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.

Surveys and Writeups

by Garibaldi, Iosevich

Alex Iosevich (about the Szemeredi-Trotter thm

by William Gasarch. Unpublished

Papers that made Progress in Rough Chronological Order that used Elementary techniques

On sets of distances of n points by Erdos. American Math Monthly 53:248-250, 1946. n/sqrt{log n} ge g_2(n) ge Omega(n^{0.5})

On the different distances determined for n points by Moser. g_2(n) ge Omega(n^{2/3})

The number of different distances determined by n points in the plane by Chung. Journal of Combinatorial Theory Series A, 36:342–354, 1984. g_2(n) ge Omega(n^{5/7})

The number of different distances determined by a set of points in the Eucidean plane. by Chung, Szemeredi, Trotter. Discrete and Computational Geometry 7:1-11, 1992. g_2(n) ge Omega(n^{0.8}/log n)

Crossing numbers and hard Erdos problems in discrete geometry by Szekely. Combinatorics, Probability, and Computing 11:1-10, 1993. g_2(n) ge Omega(n^{0.8}). This is a great paper that has a much easier proof than earlier papers.

Near optimal bounds for the Erdos distinct distances problem in high dimensions by Solymosi and Toth. Combinatorics 28:113-125, 2008. g_2(n) ge Omega(n^{6/7}). A diff paper 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}). Note 8/9 is 0.888…

On distinct distance by G. Tardos. Advances in Mathematics, 180:275-289, 2003. g_2(n) ge Omega(n^{(4e/(5e-1)) - epsilon}). Exp is roughly 0.8635

Papers that made Progress in Rough Chronological Order that used Advanced Techniques

[KT.pdf A new entropy inequality for the Erdos distance problem by

N. Katz and G.Tardos. Contemporar Mathematics Volume 342. g_2(n) ge Omega(n^{((48-14e)/(55-16e)) - epsilon}). Exp is approx 0.8641]

Elekes and Sharir There are no new lower bounds on g_2(n) in this paper; however, Guth and Katz use the Elekes-Sharir framework to obtain the result in the next item.

Guth and Katz g_2(n) ge Omega (n/ log n)

Lower bounds for g_3 and g_d.

Distinct distances in three and higher dimensions by Aronov, Pach, Sharir, Tardos cite{ED-APST}. Combinatorics, Probability, and Computing 13:283-293, 2004. g_3(n) ge Omega(n^{77/141 - epsilon}) for any epsilon>0. Exp is approx 0.546.

by Solymosi and Vu. yields the bound g_d(n) ge Omega(n^{2/d - 1/d^2})

by Solymosi and Vu. g_d(n) ge Omega(n^{2/d - 2/d(d+2)})