Erdős 單位距離問題：平面上 n 個點最多能形成多少個單位距離？

在離散幾何（discrete geometry）中，有一個非常著名但至今仍未完全解決的問題：Erdős 單位距離問題（Erdős unit distance problem）。

問題是什麼？

問題非常簡單直觀：

如果在平面上放置 n 個點，最多可以有多少對點的距離 剛好等於 1？

換句話說，我們想知道：在所有可能的點配置中，「距離為 1」的點對數量最大可以是多少。

在圖論的語言中，這等價於研究一種叫做 單位距離圖（unit distance graph） 的結構：每個點是頂點，若兩點距離為 1，就畫一條邊。

Erdős 的猜測

匈牙利傳奇數學家 Paul Erdős 在 1946 年提出這個問題。他根據整數格點（square lattice）的例子推測：

• 最大的單位距離數量應該接近

也就是說，幾乎是線性成長。

其中一個直觀例子是把點放在 √n × √n 的整數格點 上：

• 每個點與左右或上下的鄰居距離為 1
• 因此會產生大量的單位距離

這些構造能達到大約

n^{1 + O(1 / log log n)}

的數量級。