Erdős distinct distances problem

In what follows let {{math|g(n)}} denote the minimal number of distinct distances between {{math|n}} points in the plane, or equivalently the smallest possible cardinality of their distance set. In his 1946 paper, Erdős proved the estimates

:$\backslash sqrt\{n-3/4\}-1/2\backslash leq\; g(n)\backslash leq\; c\; n/\backslash sqrt\{\backslash log\; n\}$

for some constant $c$. The lower bound was given by an easy argument. The upper bound is given by a $\backslash sqrt\{n\}\backslash times\backslash sqrt\{n\}$ square grid. For such a grid, there are $O(\; n/\backslash sqrt\{\backslash log\; n\})$ numbers below n which are sums of two squares, expressed in big O notation; see Landau–Ramanujan constant. Erdős conjectured that the upper bound was closer to the true value of g(n), and specifically that (using big Omega notation) $g(n)\; =\; \backslash Omega(n^c)$ holds for every {{math|c < 1}}.

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

• {{math|1=g(n) = Ω(n^2/3)}} by Leo Moser in 1952,{{cite journal

| first=Leo | last=Moser | author-link=Leo Moser

| title=On the different distances determined by $n$ points

| journal=American Mathematical Monthly

| volume=59

| issue=2

| year=1952

| pages=85–91

| doi=10.2307/2307105

| mr=0046663

| jstor=2307105}}

• {{math|1=g(n) = Ω(n^5/7)}} by Fan Chung in 1984,{{cite journal

| first=Fan | last=Chung | author-link=Fan Chung

| title=The number of different distances determined by $n$ points in the plane

| journal=Journal of Combinatorial Theory | series=Series A

| volume=36

| issue=3

| year=1984

| pages=342–354

| url=http://www.math.ucsd.edu/~fan/mypaps/fanpap/67distances.pdf

| doi=10.1016/0097-3165(84)90041-4

| doi-access=free

| mr=0744082}}

• {{math|1=g(n) = Ω(n^4/5/log n)}} by Fan Chung, Endre Szemerédi, and William T. Trotter in 1992,{{cite journal

| first1=Fan | last1=Chung | authorlink1=Fan Chung

| first2=Endre | last2=Szemerédi | authorlink2=Endre Szemerédi

| first3=William T. | last3=Trotter | authorlink3=William T. Trotter

| title=The number of different distances determined by a set of points in the Euclidean plane

| journal=Discrete & Computational Geometry

| volume=7

| year=1992

| pages=342–354

| url=http://www.math.ucsd.edu/~fan/wp/124distances.pdf

| doi=10.1007/BF02187820

| mr=1134448

| s2cid=10637819| doi-access=free

}}

• {{math|1=g(n) = Ω(n^4/5)}} by László A. Székely in 1993,{{cite journal

| first=László A.

| last=Székely

| title=Crossing numbers and hard Erdös problems in discrete geometry

| journal=Combinatorics, Probability and Computing

| volume=11

| issue=3

| year=1993

| pages=1–10

| mr=1464571

| doi=10.1017/S0963548397002976| s2cid=36602807

}}

• {{math|1=g(n) = Ω(n^6/7)}} by József Solymosi and Csaba D. Tóth in 2001,{{cite journal

| first1 = József | last1=Solymosi | author-link=József Solymosi

| first2=Csaba D. | last2=Tóth

| title=Distinct Distances in the Plane

| journal=Discrete & Computational Geometry

| volume=25

| issue=4

| year=2001

| pages=629–634

| doi=10.1007/s00454-001-0009-z

| mr=1838423

| doi-access=free}}

• {{math|1=g(n) = Ω(n^{(4e/(5e − 1)) − ɛ})}} by Gábor Tardos in 2003,{{cite journal

| first=Gábor | last=Tardos | author-link=Gábor Tardos

| title=On distinct sums and distinct distances

| journal=Advances in Mathematics

| volume=180

| issue=1

| year=2003

| pages=275–289

| doi=10.1016/s0001-8708(03)00004-5

| mr=2019225| doi-access=free

}}

• {{math|1=g(n) = Ω(n^{((48 − 14e)/(55 − 16e)) − ɛ})}} by Nets Katz and Gábor Tardos in 2004,{{cite book

| first1 = Nets Hawk | last1=Katz | authorlink1=Nets Katz

| first2=Gábor | last2=Tardos

| year=2004

| chapter=A new entropy inequality for the Erdős distance problem

| mr=2065258

| title=Towards a theory of geometric graphs

| editor1-first=János | editor1-last=Pach

| publisher=American Mathematical Society

| location=Providence, RI

| isbn=978-0-8218-3484-8

| doi=10.1090/conm/342/06136

| pages=119–126

| series=Contemporary Mathematics

| volume=342}}

• {{math|1=g(n) = Ω(n/log n)}} by Larry Guth and Nets Katz in 2015.

Erdős also considered the higher-dimensional variant of the problem: for $d\backslash ge\; 3$ let $g\_d(n)$ denote the minimal possible number of distinct distances among $n$ points in $d$-dimensional Euclidean space. He proved that $g\_d(n)=\backslash Omega(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)=\backslash Theta(n^\{2/d\})$. József Solymosi and Van H. Vu obtained the lower bound $g\_d(n)=\backslash Omega(n^\{2/d\; -\; 2/d(d+2)\})$ in 2008.{{cite journal

| first1=József | last1=Solymosi | author-link1=József Solymosi

| first2=Van H. | last2=Vu | author-link2=Van H. Vu

| title= Near optimal bounds for the Erdős distinct distances problem in high dimensions

| journal=Combinatorica

| volume=28

| year=2008

| pages=113–125

| doi=10.1007/s00493-008-2099-1

| mr=2399013

| s2cid=2225458}}

• Falconer's conjecture
• Erdős unit distance problem
• The Erdős Distance Problem

{{Reflist}}

• William Gasarch's [http://www.cs.umd.edu/~gasarch/TOPICS/erdos_dist/erdos_dist.html page] on the problem

{{DEFAULTSORT:Erdos distinct distances problem}}

Category:Conjectures

Category:Paul Erdős

Category:Discrete geometry

Category:Eponyms in geometry