en>Danim: +{{Asteroids}}

2011-12-21T12:40:07Z

+{{Asteroids}}

New page

In [[discrete geometry]], the '''Erdős distinct distances problem''' states that between {{math|''n''}} distinct points on a plane there are at least {{math|''n''1 − [[Big_O_notation#Little-o_notation|o]](1)}} distinct distances. It was posed by [[Paul Erdős]] in 1946. In a 2010 preprint, [[Larry Guth]] and [[Nets Katz|Nets Hawk Katz]] announced a solution.<ref>{{cite arxiv|first1=l.|last1=Guth|first2=N. H.|last2=Katz|eprint=1011.4105 |title=On the Erdős distinct distance problem on the plane|year=2010}}. See also [http://terrytao.wordpress.com/2010/11/20/the-guth-katz-bound-on-the-erdos-distance-problem/ The Guth-Katz bound on the Erdős distance problem] by [[Terry Tao]] and [http://gilkalai.wordpress.com/2010/11/20/janos-pach-guth-and-katzs-solution-of-erdos-distinct-distances-problem/ Guth and Katz’s Solution of Erdős’s Distinct Distances Problem] by [[János Pach]].</ref>

==The conjecture==
In what follows let {{math|''g''(''n'')}} denote the minimal number of distinct distances between {{math|''n''}} points in the plane. In his 1946 paper, Erdős proved the estimates
<math>\sqrt{n-3/4}-1/2\leq g(n)\leq c n/\sqrt{\log n}</math> for some constant <math>c</math>. The lower bound was given by an easy argument, the upper bound is given by a <math>\sqrt{n}\times\sqrt{n}</math> square grid (as there are <math>O( n/\sqrt{\log n})</math> 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, <math>g(n) = \Omega(n^c)</math> holds for every {{math|''c'' < 1}}.

==Partial results==
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)}} ([[Leo Moser]], 1952),
*{{math|1=''g''(''n'') = Ω(''n''5/7)}} ([[Fan Chung]], 1984),
*{{math|1=''g''(''n'') = Ω(''n''4/5/log ''n'')}} ([[Fan Chung]], [[Endre Szemerédi]], [[W. T. Trotter]], 1992),
*{{math|1=''g''(''n'') = Ω(''n''4/5)}} ([[László Székely]], 1993),
*{{math|1=''g''(''n'') = Ω(''n''6/7)}} ([[József Solymosi]], C. D. Tóth, 2001),
*{{math|1=''g''(''n'') = Ω(''n''(4''e''/(5''e'' − 1)) − ''e'')}} ([[Gábor Tardos]], 2003),
*{{math|1=''g''(''n'') = Ω(''n''((48 − 14''e'')/(55 − 16''e'')) − ''e'')}} ([[Nets Katz|Nets Hawk Katz]], [[Gábor Tardos]], 2004),
*{{math|1=''g''(''n'') = Ω(''n''/log ''n'')}} ([[Larry Guth]], [[Nets Katz|Nets Hawk Katz]], 2010).

==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 {{math|1=''g''''d''(''n'') = Ω(''n''1/''d'')}} and {{math|1=''g''''d''(''n'') = O(''n''2/''d'')}} and conjectured that the upper bound is in fact sharp, i.e., {{math|1=''g''''d''(''n'') = Θ(''n''2/''d'')}} . In 2008, Solymosi and [[Van H. Vu|Vu]] obtained the {{math|1=''g''''d''(''n'') = Ω(''n''2/''d''(1-1/(''d''+2)))}} lower bound.

==See also==
*[[Falconer's conjecture]]
*The [[Unit_distance_graph#Counting unit distances|Erdős unit distance problem]]

==Notes==
{{reflist}}

==References==
*{{citation|first=F.|last=Chung|authorlink=Fan Chung|title=The number of different distances determined by {{math|''n''}} points in the plane |journal=[[Journal of Combinatorial Theory]], (A)|volume=36|year=1984|pages=342–354|url=http://www.math.ucsd.edu/~fan/mypaps/fanpap/67distances.pdf|doi=10.1016/0097-3165(84)90041-4}}.
*{{citation|first1=F.|last1=Chung|authorlink1=Fan Chung|first2=E.|last2=Szemerédi|authorlink2=Endre Szemerédi|first3=W. T.|last3=Trotter|title=The number of different distances determined by a set of points in the Euclidean plane|journal=[[Discrete and Computational Geometry]]|volume=7|year=1984|pages=342–354|url=http://www.math.ucsd.edu/~fan/wp/124distances.pdf|doi=10.1007/BF02187820}}.
*{{citation|first=P.|last=Erdős|authorlink=Paul Erdős|url=http://www.renyi.hu/~p_erdos/1946-03.pdf|title=On sets of distances of {{math|''n''}} points|journal=[[American Mathematical Monthly]]|volume=53|year=1946|pages=248–250|doi=10.2307/2305092}}.
*{{citation|first1=J.|last1=Garibaldi|first2=A.|last2=Iosevich|first3=S.|last3=Senger|title=The Erdős Distance Problem|year=2011|publisher=American Mathematical Society |place=Providence, RI }}.
*{{cite arxiv|first1=L.|last1=Guth|first2=N. H.|last2=Katz|eprint=1011.4105 |title=On the Erdős distinct distance problem on the plane|year=2010}}.
*{{citation|first=L.|last=Moser|authorlink=Leo Moser|title=On the different distances determined by {{math|''n''}} points|journal=[[American Mathematical Monthly]]|volume=59|year=1952|pages=85–91}}.
*{{citation|first1=J.|last1=Solymosi|authorlink=József Solymosi|first2=Cs. D.|last2=Tóth|title=Distinct Distances in the Plane |journal=[[Discrete and Computational Geometry]]|volume=25|year=2001|pages=629–634}}.
*{{citation|first1=J.|last1=Solymosi|authorlink=József Solymosi|first2=Van H.|last2=Vu|title= Near optimal bounds for the Erdős distinct distances problem in high dimensions
|journal=[[Combinatorica]]|volume=28|year=2008|pages=113–125}}.
*{{citation|first=L.|last=Székely|title=Crossing numbers and hard Erdös problems in discrete geometry|journal=Combinatorics, Probability and Computing|volume=11|year=1993|pages=1–10}}.
*{{citation|first=G.|last=Tardos|authorlink=Gábor Tardos|title=On distinct sums and distinct distances |journal=Advances in Mathematics|volume=180|year=2003|pages=275–289}}.

==External links==
* William Gasarch's [http://www.cs.umd.edu/~gasarch/erdos_dist/erdos_dist.html page] on the problem
* [[János Pach]]'s [http://gilkalai.wordpress.com/2010/11/20/janos-pach-guth-and-katzs-solution-of-erdos-distinct-distances-problem/ guest post] on [[Gil Kalai]]'s blog
* [[Terence Tao|Terry Tao]]'s blog [http://terrytao.wordpress.com/2010/11/20/the-guth-katz-bound-on-the-erdos-distance-problem/ entry] on the Guth-Katz proof, gives a detailed exposition of the proof.

{{DEFAULTSORT:Erdos distinct distances problem}}
[[Category:Conjectures]]
[[Category:Paul Erdős]]
[[Category:Discrete geometry]]

Dynamic method - Revision history

en>Danim: +{{Asteroids}}