Проблема различимых расстояний в лесу

В дискретной геометрии задача Эрдёша о различных расстояниях утверждает, что каждый набор точек на плоскости имеет почти линейное количество различных расстояний. Его поставил Пол Эрдеш в 1946 году. ^{[ 1 ]}^{[ 2 ]} и почти доказано Ларри Гутом и Нетсом Кацем в 2015 году. ^{[ 3 ]}^{[ 4 ]}^{[ 5 ]}

Гипотеза

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

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

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

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

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

$г (п) = Ω(п 2/3)$ Лео Мозера в 1952 году, ^{[ 6 ]}
$г (п) = Ω(п 5/7)$ в Фань Чунга 1984 году, ^{[ 7 ]}

$г (п) = Ω(п 4/5 /log n)$ Фань Чанг, Эндре Семереди и Уильям Т. Троттер в 1992 году, ^{[ 8 ]}
$г (п) = Ω(п 4/5)$ Ласло А. Секели в 1993 году, ^{[ 9 ]}
$г (п) = Ω(п 6/7)$ Йожефа Солимоши и Чабы Д. Тота в 2001 году, ^{[ 10 ]}
$г (п) = Ω(п (4 е /(5 е - 1)) - ɛ)$ Габора Тардоса в 2003 году, ^{[ 11 ]}
$г (п) = Ω(п ((48 - 14 е)/(55 - 16 е)) - ɛ)$ Нетса Каца и Габора Тардоса в 2004 году, ^{[ 12 ]}
$g (n) = Ω(n /log n)$ Ларри Гута и Нетса Каца в 2015 году. ^{[ 3 ]}

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

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