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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Гипотеза[править | править исходный текст]

Пусть g(n) минимальное число различных расстояний между n точками на плоскости. В 1946 году Эрдёш доказал оценки \sqrt{n-3/4}-1/2\leq g(n)\leq c n/\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) = Ω(n1/2) последовательно улучшалась:

Другие размерности[править | править исходный текст]

Эрдёш рассмотрел также проблему для более высоких размерностей пространства. Пусть gd(n) минимальное число различных расстояний для n точек в Евклидовом пространстве размерности d. Он доказал, что 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))).

Смотри также[править | править исходный текст]

Примечания[править | править исходный текст]

Ссылки[править | править исходный текст]

.

  • 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 .

Внешние ссылки[править | править исходный текст]