Гипотеза Эрдёша о числе различных расстояний

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

Гипотеза

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

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

Эрдёш рассмотрел также проблему для более высоких размерностей пространства. Пусть $g_{d}(n)$ минимальное число различных расстояний для $n$ точек в евклидовом пространстве размерности $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" (PDF), Journal of Combinatorial Theory, (A), 36: 342—354, doi:10.1016/0097-3165(84)90041-4 {{citation}}: templatestyles stripmarker в |title= на позиции 49 (справка) Архивная копия от 3 марта 2012 на Wayback Machine.
• Chung, F.; Szemerédi, E.; Trotter, W. T. (1984), "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 Архивная копия от 3 марта 2012 на Wayback Machine
• Erdős, P. (1946), "On sets of distances of n points" (PDF), American Mathematical Monthly, 53: 248—250 {{citation}}: templatestyles stripmarker в |title= на позиции 25 (справка) Архивная копия от 5 марта 2012 на Wayback Machine
• 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". arXiv:1011.4105.
• Moser, L. (1952), "On the different distances determined by n points", American Mathematical Monthly, 59: 85—91 {{citation}}: templatestyles stripmarker в |title= на позиции 42 (справка).
• 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 Архивная копия от 9 мая 2013 на Wayback Machine (в блоге Гиля Калая)
• Подробное доказательство Гута — Каца Архивная копия от 25 апреля 2013 на Wayback Machine в блоге Теренса Тао