Задача о единичных расстояниях между точками на плоскости

В дискретной геометрии существует известная открытая задача — задача о единичных расстояниях Эрдёша. Она звучит просто, но уже десятилетиями остаётся нерешённой.

Суть вопроса следующая: если на евклидовой плоскости расположить n точек, сколько пар точек могут находиться на расстоянии ровно 1 друг от друга максимум?

Иначе говоря, нужно понять, как быстро растёт максимальное количество таких «единичных расстояний» по мере увеличения числа точек.

Гипотеза Эрдёша

Когда математик Пол Эрдёш сформулировал эту задачу в 1946 году, он предположил, что максимальное число таких пар растёт почти линейно. Его гипотеза утверждает, что порядок величины должен быть

n^(1+o(1)) .

Эта идея возникла из конструкций на квадратной решётке. Если разместить точки в узлах решётки (например, в квадратной сетке), то многие соседние точки оказываются на расстоянии 1 — по горизонтали и вертикали. Такие примеры дают немного больше, чем линейное число единичных расстояний .

Лучший известный верхний предел

Несмотря на десятилетия исследований, точный порядок величины неизвестен.

Самый сильный общий результат был получен в 1984 году. Математики Джоэл Спенсер, Эндре Семереди и Уильям Троттер доказали, что число единичных расстояний среди n точек на плоскости не может превышать