Erdős distinct distances problem

In discrete geometry, the Erdős distinct distances problem states that between n distinct points on a plane there are at least n^{1 − o(1)} distinct distances. It was posed by Paul Erdős in 1946. In a 2010 preprint, Larry Guth and Net Hawk Katz announced a solution.

The conjecture

In what follows let g(n) denote the minimal number of distinct distances between n points in the plane. In his 1946 paper, Erdős proved the estimates ${\sqrt {n-3/4}}-1/2\leq g(n)\leq cn/{\sqrt {\log n}}$ for some constant $c$. The lower bound was given by an easy argument, the upper bound is given by a ${\sqrt {n}}\times {\sqrt {n}}$ square grid (as there are $O(n/{\sqrt {\log n}})$ numbers below n which are sums of two squares, see Landau–Ramanujan constant). Erdős conjectured that the upper bound was closer to the true value of g(n), specifically, $g(n)=\Omega (n^{c})$ holds for every c < 1.

Partial results

Paul Erdős' 1946 lower bound of g(n) = Ω(n^1/2) was successively improved to:

• g(n) = Ω(n^2/3) (Leo Moser, 1952),
• g(n) = Ω(n^5/7) (Fan Chung, 1984),
• g(n) = Ω(n^4/5/log n) (Fan Chung, Endre Szemerédi, W. T. Trotter, 1992),
• g(n) = Ω(n^4/5) (László Székely, 1993),
• g(n) = Ω(n^6/7) (József Solymosi, C. D. Tóth, 2001),
• g(n) = Ω(n^{(4e/(5e − 1)) − e}) (Gábor Tardos, 2003), and
• g(n) = Ω(n^{((48 − 14e)/(55 − 16e)) − e}) (Nets Hawk Katz, Gábor Tardos, 2004).

Higher dimensions

Erdős also considered the higher dimensional variant of the problem: for d≥3 let g_d(n) denote the minimal possible number of distinct distances among n point in the d-dimensional Euclidean space. He proved that g_d(n) = Ω(n^1/d) and g_d(n) = O(n^2/d) and conjectured that the upper bound is in fact sharp, i.e., g_d(n) = Θ(n^2/d) . In 2008, Solymosi and Vu obtained the g_d(n) = Ω(n^{2/d(1-1/(d+2))}) lower bound.

See also

• The Erdős unit distance problem

References

• Chung, F. (1984), "The number of different distances determined by n points in the plane" (PDF), Journal of Combinatorial Theory, (A), 36: 342–354, doi:10.1016/0097-3165(84)90041-4.
• Chung, F.; Szemerédi, E.; Trotter, W. T. (1984), "The number of different distances determined by a set of points in the Euclidean plane" (PDF), Discrete and Computational Geometry, 7: 342–354, doi:10.1007/BF02187820 {{citation}}: Cite has empty unknown parameter: |1= (help).
• Erdős, P. (1946), "On sets of distances of n points" (PDF), American Mathematical Monthly, 53: 248–250.
• Garibaldi, J.; Iosevich, A.; Senger, S. (2011), The Erdős Distance Problem, Providence, RI: American Mathematical Society.
• Guth, l.; Katz, N. H. (2010), On the Erdős distinct distance problem on the plane, arXiv:1011.4105.
• Moser, L. (1952), "On the different distances determined by n points", American Mathematical Monthly, 59: 85–91.
• Solymosi, J.; Tóth, Cs. D. (2001), "Distinct Distances in the Plane", Discrete and Computational Geometry, 25: 629–634.
• Solymosi, J.; Vu, Van H. (2008), "Near optimal bounds for the Erdős distinct distances problem in high dimensions", Combinatorica, 28: 113–125.
• Székely, L. (1993), "Crossing numbers and hard Erdös problems in discrete geometry", Combinatorics, Probability and Computing, 11: 1–10.
• Tardos, G. (2003), "On distinct sums and distinct distances", Advances in Mathematics, 180: 275–289 {{citation}}: Cite has empty unknown parameter: |1= (help).

External links

• William Gasarch's page on the problem
• János Pach's guest post on Gil Kalai's blog
• Terry Tao's blog entry on the Guth-Katz proof, gives a detailed exposition of the proof.