エルデシュのユニット距離問題：平面上の点はいくつ「距離1」で結べるのか

例えば、正方格子（√n × √n の格子）に点を並べると、隣接する点どうしの水平・垂直方向で多くの距離1のペアが生まれます。このような構成により、n にほぼ比例する数のユニット距離を作れることが知られています 。

現在知られている最良の上界

しかし「どんな配置でもそれ以上にはならない」という上限を示す証明は難しく、現在の最良結果は次の通りです。

1984年、スペンサー、セメレディ、トロッターが次を証明しました。

最大数 ≤ O(n^(4/3))

つまり、どんな点配置でもユニット距離の数は n^(4/3) のオーダーを超えないことが示されています 。

現在の研究状況

まとめると、現在知られている範囲は次の通りです。

下界:  n^(1 + Ω(1 / log log n))
上界:  O(n^(4/3))
予想:  n^(1 + o(1))

この 上界と予想の間のギャップが、問題の核心です。数学者たちは長年この差を縮めようと研究を続けていますが、決定的な突破口はまだ見つかっていません 。

結論

エルデシュのユニット距離問題は、1946年に提起されて以来、離散幾何学と組合せ幾何学の中心的な未解決問題の一つです。

• 問題：n 個の点が作れる距離1のペアの最大数
• 最良の上界：O(n^(4/3))
• エルデシュの予想：n^(1+o(1))

したがって、この予想を完全に証明する一般解は現在も存在していません 。