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

Гипотеза Эрдёша о числе различных расстояний — утверждение комбинаторной геометрии, согласно которому между различными точками на плоскости имеется не меньше, чем различных расстояний. Гипотеза сформулирована Палом Эрдёшем в 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.

Литература

править

Ссылки

править