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

Пусть ${\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 (в блоге Гиля Калая)
• Подробное доказательство Гута — Каца в блоге Теренса Тао