WikiSort.ru - Не сортированное

Гипотеза Эрдёша о числе различных расстояний — утверждение комбинаторной геометрии, согласно которому между ${\displaystyle n}$ различными точками на плоскости имеется не меньше, чем ${\displaystyle n^{1-o(1)}}$ различных расстояний. Гипотеза сформулирована Палом Эрдёшем в 1946 году, в 2010 году Ларри Гут (англ. Larry Guth) и Нетс Катц (англ. Nets Hawk Katz) объявили о возможном решении этой проблемы^[1], окончательное доказательство Гута и Каца было завершено в 2015 году.

Гипотеза

Пусть ${\displaystyle g(n)}$ минимальное число различных расстояний между ${\displaystyle n}$ точками на плоскости. В 1946 году Эрдёш доказал оценки ${\displaystyle {\sqrt {n-3/4}}-1/2\leqslant g(n)\leqslant cn/{\sqrt {\log n}}}$ для некоторой константы ${\displaystyle c}$ . Нижняя оценка получена простым доказательством, верхняя оценка получена на базе квадратной решётки ${\displaystyle {\sqrt {n}}\times {\sqrt {n}}}$ и того, что число целых меньше ${\displaystyle n}$ равных сумме двух квадратов равно ${\displaystyle O(n/{\sqrt {\log n}})}$ согласно результату Ландау — Рамануджана. Эрдёш предположил, что верхняя граница ближе к истинной величине ${\displaystyle g(n)}$ и ${\displaystyle g(n)=\Omega (n^{c})}$ верно для любого ${\displaystyle c<1}$ .

Результаты

Нижняя граница Эрдёша g(n) = Ω(n^1/2) последовательно улучшалась:

• g(n) = Ω(n^2/3) — Лео Мозер (англ. Leo Moser), 1952;
• g(n) = Ω(n^5/7) — Фан Чун (англ. Fan Chung), 1984;
• g(n) = Ω(n^4/5/log n) — Фан Чун, Эндре Семереди, Уильям Троттер, 1992;
• g(n) = Ω(n^4/5) — Ласло Секей, 1993;
• g(n) = Ω(n^6/7) — Йожеф Шоймоши, Чаба Тот, 2001;
• g(n) = Ω(n^{(4e/(5e − 1)) − e}) — Габор Тардош (англ. Gábor Tardos), 2003;
• g(n) = Ω(n^{((48 − 14e)/(55 − 16e)) − e}) — Нетс Кац, Габор Тардош, 2004;
• g(n) = Ω(n/log n) — Ларри Гут, Нетс Кац, 2015.

Другие размерности

Эрдёш рассмотрел также проблему для более высоких размерностей пространства. Пусть ${\displaystyle g_{d}(n)}$ минимальное число различных расстояний для ${\displaystyle n}$ точек в евклидовом пространстве размерности ${\displaystyle d}$ . Он доказал, что g_d(n) = Ω(n^1/d) и g_d(n) = O(n^2/d) и предположил, что верхняя граница является близкой, то есть g_d(n) = Θ(n^2/d). В 2008 году Шоймоши и Ван Ву (англ. Van Vu)) получили нижнюю оценку g_d(n) = O(n^{2/d(1-1/(d+2))}).

См. также

• Гипотеза Фальконера (англ. Falconer's conjecture)
• Граф единичных расстояний

Примечания

Ссылки

• Chung, F. (1984), "The number of different distances determined by n points in the plane", Journal of Combinatorial Theory, (A) Т. 36: 342–354, doi:10.1016/0097-3165(84)90041-4, <http://www.math.ucsd.edu/~fan/mypaps/fanpap/67distances.pdf> .
• Chung, F.; Szemerédi, E. & Trotter, W. T. (1984), "The number of different distances determined by a set of points in the Euclidean plane", Discrete and Computational Geometry Т. 7: 342–354, doi:10.1007/BF02187820, <http://www.math.ucsd.edu/~fan/wp/124distances.pdf> 
• Erdős, P. (1946), "On sets of distances of n points", American Mathematical Monthly Т. 53: 248–250, <http://www.renyi.hu/~p_erdos/1946-03.pdf> 
• 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", arΧiv: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 .

Ссылки

• William Gasarch. A Webpage on The Erdos Distance Problem
• János Pach: Guth and Katz’s Solution of Erdős’s Distinct Distances Problem (в блоге Гиля Калая^[en])
• Подробное доказательство Гута — Каца в блоге Теренса Тао