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

Гипотеза Эрдёша о числе различных расстояний — утверждение комбинаторной геометрии, согласно которому между ${\displaystyle n}$ различными точками на плоскости имеется не меньше, чем ${\displaystyle n^{1-o(1)}}$ различных расстояний. Гипотеза сформулирована Палом Эрдёшем в 1946 году, в 2010 году Ларри Гут и Нетс Катц (англ. 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 (PDF), Journal of Combinatorial Theory, (A), 36 (3): 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 [math.CO].
• Moser, L. (1952), On the different distances determined by n points, American Mathematical Monthly, 59 (2): 85–91, doi:10.1080/00029890.1952.11988075 {{citation}}: templatestyles stripmarker в |title= на позиции 42 (справка).
• Solymosi, J.; Tóth, Cs. D. (2001), Distinct Distances in the Plane, Discrete and Computational Geometry, 25 (4): 629–634, doi:10.1007/s00454-001-0009-z.
• Solymosi, J.; 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.
• 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, doi:10.1016/S0001-8708(03)00004-5.

• 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 в блоге Теренса Тао