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

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

Гипотеза

Пусть $g (n)$ минимальное число различных расстояний между $n$ точками на плоскости. В 1946 году Эрдёш доказал оценки $\sqrt{n - 3 / 4} - 1 / 2 ⩽ g (n) ⩽ c n / \sqrt{\log n}$ для некоторой константы $c$ . Нижняя оценка получена простым доказательством, верхняя оценка получена на базе квадратной решётки $\sqrt{n} \times \sqrt{n}$ и того, что число целых меньше $n$ равных сумме двух квадратов равно $O (n / \sqrt{\log n})$ согласно результату Ландау — Рамануджана. Эрдёш предположил, что верхняя граница ближе к истинной величине $g (n)$ и $g (n) = Ω (n^{c})$ верно для любого $c < 1$ .

Результаты

Нижняя граница Эрдёша Шаблон:Math последовательно улучшалась:

Шаблон:Math — Шаблон:Нп2, 1952;
Шаблон:Math — Шаблон:Нп2, 1984;
Шаблон:Math — Фан Чун, Эндре Семереди, Уильям Троттер, 1992;
Шаблон:Math — Ласло Секей, 1993;
Шаблон:Math — Йожеф Шоймоши, Чаба Тот, 2001;
Шаблон:Math — Шаблон:Нп2, 2003;
Шаблон:Math — Нетс Кац, Габор Тардош, 2004;
Шаблон:Math — Ларри Гут, Нетс Кац, 2015.

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

Эрдёш рассмотрел также проблему для более высоких размерностей пространства. Пусть $g_{d} (n)$ минимальное число различных расстояний для $n$ точек в евклидовом пространстве размерности $d$ . Он доказал, что Шаблон:Math и Шаблон:Math и предположил, что верхняя граница является близкой, то есть Шаблон:Math. В 2008 году Шоймоши и Шаблон:Нп2 получили нижнюю оценку Шаблон:Math.

См. также

Примечания

Шаблон:Примечания

Литература

Ссылки

William Gasarch. A Webpage on The Erdos Distance Problem
János Pach: Guth and Katz’s Solution of Erdős’s Distinct Distances Problem Шаблон:Wayback (в блоге Шаблон:Iw)
Подробное доказательство Гута — Каца Шаблон:Wayback в блоге Теренса Тао

↑ Шаблон:Cite arXiv. См. также Граница Гута-Каца для проблемы Эрдёша о расстояниях Шаблон:Wayback и Решение Гута-Каца проблемы Эрдёша о различных расстояниях Шаблон:Wayback.

[1] Шаблон:Cite arXiv. См. также Граница Гута-Каца для проблемы Эрдёша о расстояниях Шаблон:Wayback и Решение Гута-Каца проблемы Эрдёша о различных расстояниях Шаблон:Wayback.

[1]

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

Содержание