Задача Ердеша про одиничні відстані: чи існує повне доведення?

Гіпотеза Ердеша, висунута 1946 року, стверджує, що ця кількість майже лінійно залежить від (n), тобто приблизно (n^{1+o(1)}). Це припущення базувалося на прикладах точок, розташованих у вигляді ґратки, які дають багато одиничних відстаней .

Однак найкраща загальна верхня межа, яку вдалося знайти математикам, досі залишається на рівні (O(n^{4/3})). Її довели Спенсер, Семереді та Троттер ще в 1984 році . За останні 40 років покращити цей результат нікому не вдалося .

Таким чином, поточний стан проблеми можна зобразити так :

Нижня межа:  n^(1 + O(1/log log n))
Верхня межа: O(n^(4/3))
Гіпотеза:    n^(1+o(1))

Тому, якщо ви питаєте про доведення повної гіпотези Ердеша про одиничні відстані, то відповідь: недостатньо доказів / доведення невідоме .

Простий приклад: розмістіть точки у вигляді квадратної цілочисельної ґратки. Багато пар точок будуть на відстані 1 одна від одної по горизонталі та вертикалі, що дає лінійну кількість одиничних відстаней. Конструкції Ердеша на основі ґраток дозволяють отримати трохи більше, ніж лінійну кількість .