Английская Википедия: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[1][2] and almost proven by Larry Guth and Nets Katz in 2015.[3][4][5]
The conjecture
In what follows let Шаблон:Math denote the minimal number of distinct distances between Шаблон:Math points in the plane, or equivalently the smallest possible cardinality of their distance set. 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. For such a grid, there are <math>O( n/\sqrt{\log n})</math> 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) <math>g(n) = \Omega(n^c)</math> holds for every Шаблон:Math.
Partial results
Paul Erdős' 1946 lower bound of Шаблон:Math was successively improved to:
- Шаблон:Math by Leo Moser in 1952,[6]
- Шаблон:Math by Fan Chung in 1984,[7]
- Шаблон:Math by Fan Chung, Endre Szemerédi, and William T. Trotter in 1992,[8]
- Шаблон:Math by László A. Székely in 1993,[9]
- Шаблон:Math by József Solymosi and Csaba D. Tóth in 2001,[10]
- Шаблон:Math by Gábor Tardos in 2003,[11]
- Шаблон:Math by Nets Katz and Gábor Tardos in 2004,[12]
- Шаблон:Math by Larry Guth and Nets Katz in 2015.[3]
Higher dimensions
Erdős also considered the higher-dimensional variant of the problem: for <math>d\ge 3</math> let <math>g_d(n)</math> denote the minimal possible number of distinct distances among <math>n</math> points in <math>d</math>-dimensional Euclidean space. He proved that <math>g_d(n)=\Omega(n^{1/d})</math> and <math>g_d(n)=O(n^{2/d})</math> and conjectured that the upper bound is in fact sharp, i.e., <math>g_d(n)=\Theta(n^{2/d})</math>. József Solymosi and Van H. Vu obtained the lower bound <math>g_d(n)=\Omega(n^{2/d - 2/d(d+2)})</math> in 2008.[13]
See also
References
External links
- William Gasarch's page on the problem
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Citation
- ↑ 3,0 3,1 Шаблон:Cite journal
- ↑ The Guth-Katz bound on the Erdős distance problem, a detailed exposition of the proof, by Terence Tao
- ↑ Guth and Katz’s Solution of Erdős’s Distinct Distances Problem, a guest post by János Pach on Gil Kalai's blog
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Cite book
- ↑ Шаблон:Cite journal
