Проблема различных расстояний Эрдеша - Erdős distinct distances problem

В дискретная геометрия, то Проблема различных расстояний Эрдеша утверждает, что каждый набор точек на плоскости имеет почти линейное количество различных расстояний. Это было поставлено Пол Эрдёш в 1946 году и почти доказано Гут и Кац (2015).

Гипотеза

В дальнейшем пусть грамм(п) обозначают минимальное количество различных расстояний между п точки на плоскости или, что то же самое, наименьшее возможное мощность от их набор расстояний. В своей статье 1946 года Эрдеш доказал оценки

для некоторой постоянной . Нижняя оценка была получена с помощью простого аргумента. Верхняя граница дается квадратная сетка. Для такой сетки есть числа ниже п которые представляют собой суммы двух квадратов, выраженные в нотация большой O; видеть Постоянная Ландау – Рамануджана. Эрдеш предположил, что верхняя граница была ближе к истинному значению грамм(п) и, в частности, что (используя большая нотация омега ) справедливо для каждого c < 1.

Частичные результаты

Нижняя граница Пола Эрдеша 1946 г. грамм(п) = Ω (п1/2) был последовательно улучшен до:

Высшие измерения

Эрдеш также рассмотрел многомерный вариант задачи: для позволять обозначают минимально возможное количество различных расстояний между указывает в -размерный Евклидово пространство. Он доказал, что и и предположил, что верхняя оценка на самом деле точна, т. е. . Солимози и Ву (2008) получил нижнюю оценку .

Смотрите также

Рекомендации

внешняя ссылка