WikiDer > Проблема различных расстояний Эрдеша

Erdős distinct distances problem

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

Гипотеза

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

{ displaystyle { sqrt {n-3/4}} - 1/2 leq g (n) leq cn / { sqrt { log n}}}

для некоторой постоянной ${ displaystyle c}$ . Нижняя оценка была получена с помощью простого аргумента. Верхняя граница дается ${ displaystyle { sqrt {n}} times { sqrt {n}}}$ квадратная сетка. Для такой сетки есть ${ Displaystyle О (п / { sqrt { log п}})}$ числа ниже п которые представляют собой суммы двух квадратов, выраженные в нотация большой O; видеть Постоянная Ландау – Рамануджана. Эрдеш предположил, что верхняя граница была ближе к истинному значению грамм(п) и, в частности, что (используя большая нотация омега) ${ Displaystyle г (п) = Омега (п ^ {с})}$ справедливо для каждого $c < 1$ .

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

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

$грамм (п) = Ω (п 2/3)$ (Мозер 1952)
$грамм (п) = Ω (п 5/7)$ (Чанг 1984)
$грамм (п) = Ω (п 4/5 /бревно п)$ (Чанг, Семереди и Троттер, 1992 г.)
$грамм (п) = Ω (п 4/5)$ (Секели 1993)
$грамм (п) = Ω (п 6/7)$ (Солимози и Тот 2001)
$грамм (п) = Ω (п (4 е /(5 е - 1)) - ɛ)$ (Тардос 2003)
$грамм (п) = Ω (п ((48 - 14 е)/(55 - 16 е)) - ɛ)$ (Кац и Тардос 2004)
$грамм (п) = Ω (п /бревно п)$ (Гут и Кац 2015)

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

Эрдеш также рассмотрел многомерный вариант задачи: для ${ displaystyle d geq 3}$ позволять ${ displaystyle g_ {d} (п)}$ обозначают минимально возможное количество различных расстояний между ${ displaystyle n}$ указывает в ${ displaystyle d}$ -размерный Евклидово пространство. Он доказал, что ${ displaystyle g_ {d} (n) = Omega (n ^ {1 / d})}$ и ${ displaystyle g_ {d} (n) = O (n ^ {2 / d})}$ и предположил, что верхняя оценка на самом деле точна, т. е. ${ displaystyle g_ {d} (n) = Theta (n ^ {2 / d})}$ . Солимози и Ву (2008) получил нижнюю оценку ${ displaystyle g_ {d} (n) = Omega (n ^ {2 / d-2 / d (d + 2)})}$ .