Гипотеза Эрдёша о числе различных расстояний (Inhkmy[g |j;~og k cnvly jg[lncud] jgvvmkxunw)

Перейти к навигации Перейти к поиску

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

Пусть минимальное число различных расстояний между точками на плоскости. В 1946 году Эрдёш доказал оценки для некоторой константы . Нижняя оценка получена простым доказательством, верхняя оценка получена на базе квадратной решётки и того, что число целых меньше равных сумме двух квадратов равно согласно результату Ландау — Рамануджана. Эрдёш предположил, что верхняя граница ближе к истинной величине и верно для любого .

Результаты

[править | править код]

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

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

[править | править код]

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

Примечания

[править | править код]
  1. Guth, l.; Katz, N. H. (2010). "On the Erdős distinct distance problem on the plane". arXiv:1011.4105.. См. также Граница Гута-Каца для проблемы Эрдёша о расстояниях Архивная копия от 25 апреля 2013 на Wayback Machine и Решение Гута-Каца проблемы Эрдёша о различных расстояниях Архивная копия от 9 мая 2013 на Wayback Machine.

Литература

[править | править код]