Erdős distinct distances problem

In discrete geometry, the Erdős distinct distances problem states that every set of points in the plane has a nearly-linear number of distinct distances. It was posed by Paul Erdős in 1946 and almost proven by Guth & Katz (2015).

The conjecture

In what follows let $g (n)$ denote the minimal number of distinct distances between $n$ points in the plane, or equivalently the smallest possible cardinality of their distance set. 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. For such a grid, there are $O(n/{\sqrt {\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)=\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)$ (Moser 1952)
$g (n) = Ω (n 5/7)$ (Chung 1984)
$g (n) = Ω (n 4/5 /log n)$ (Chung, Szemerédi & Trotter 1992)
$g (n) = Ω (n 4/5)$ (Székely 1993)
$g (n) = Ω (n 6/7)$ (Solymosi & Tóth 2001)
$g (n) = Ω (n (4 e /(5 e - 1)) - ɛ)$ (Tardos 2003)
$g (n) = Ω (n ((48 - 14 e)/(55 - 16 e)) - ɛ)$ (Katz & Tardos 2004)
$g (n) = Ω (n /log n)$ (Guth & Katz 2015)

Higher dimensions

Erdős also considered the higher-dimensional variant of the problem: for $d\geq 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)=\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)=\Theta (n^{2/d})$ . Solymosi & Vu (2008) obtained the lower bound $g_{d}(n)=\Omega (n^{2/d-2/d(d+2)})$ .

gollark: I decided to try OCR software on memes and it works poorly.

gollark: Huh, apparently my school *already* has timetables and teacher/class assignments for next school year. That might be overoptimistic of them but who knows.

gollark: It seems like one of those things which can't possibly *entirely* work, since you can't just give someone some data (an image) and then prevent them doing stuff you don't like with it, but can work a bit and at least frustrate people without specific domain knowledge.

gollark: Hmm, if you use it in a browser somehow it might not even be able to detect being screenshotted since those have better sandboxing.

gollark: Anyway, the whole "blocking screenshots" thing (or at least notifying people when they get their stuff screenshotted) seems doomed to failure like DRM. Why do Android and iOS even *tell* the app it's being screenshotted? That seems bound to be abused.

References

Chung, Fan (1984), "The number of different distances determined by $n$ points in the plane" (PDF), Journal of Combinatorial Theory, Series A, 36 (3): 342–354, doi:10.1016/0097-3165(84)90041-4, MR 0744082CS1 maint: ref=harv (link).
Chung, Fan; Szemerédi, Endre; Trotter, William T. (1992), "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, MR 1134448CS1 maint: ref=harv (link).
Erdős, Paul (1946), "On sets of distances of $n$ points" (PDF), American Mathematical Monthly, 53 (5): 248–250, doi:10.2307/2305092, JSTOR 2305092.
Garibaldi, Julia; Iosevich, Alex; Senger, Steven (2011), The Erdős Distance Problem, Student Mathematical Library, 56, Providence, RI: American Mathematical Society, ISBN 978-0-8218-5281-1, MR 2721878.
Guth, Larry; Katz, Nets Hawk (2015), "On the Erdős distinct distances problem in the plane", Annals of Mathematics, 181 (1): 155–190, arXiv:1011.4105, doi:10.4007/annals.2015.181.1.2, MR 3272924, Zbl 1310.52019CS1 maint: ref=harv (link). See also The Guth-Katz bound on the Erdős distance problem by Terry Tao and Guth and Katz’s Solution of Erdős’s Distinct Distances Problem by János Pach.
Katz, Nets Hawk; Tardos, Gábor (2004), "A new entropy inequality for the Erdős distance problem", in Pach, János (ed.), Towards a theory of geometric graphs, Contemporary Mathematics, 342, Providence, RI: American Mathematical Society, pp. 119–126, doi:10.1090/conm/342/06136, ISBN 978-0-8218-3484-8, MR 2065258
Moser, Leo (1952), "On the different distances determined by $n$ points", American Mathematical Monthly, 59 (2): 85–91, doi:10.2307/2307105, JSTOR 2307105, MR 0046663CS1 maint: ref=harv (link).
Solymosi, József; Tóth, Csaba D. (2001), "Distinct Distances in the Plane", Discrete and Computational Geometry, 25 (4): 629–634, doi:10.1007/s00454-001-0009-z, MR 1838423CS1 maint: ref=harv (link).
Solymosi, József; Vu, Van H. (2008), "Near optimal bounds for the Erdős distinct distances problem in high dimensions", Combinatorica, 28: 113–125, doi:10.1007/s00493-008-2099-1, MR 2399013CS1 maint: ref=harv (link).
Székely, László A. (1993), "Crossing numbers and hard Erdös problems in discrete geometry", Combinatorics, Probability and Computing, 11 (3): 1–10, doi:10.1017/S0963548397002976, MR 1464571CS1 maint: ref=harv (link).
Tardos, Gábor (2003), "On distinct sums and distinct distances", Advances in Mathematics, 180: 275–289, doi:10.1016/s0001-8708(03)00004-5, MR 2019225.

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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.