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

エルデシュのユニット距離問題は、平面上の n 個の点の間で距離1になるペアの最大数を問う問題。

最初に検証する重要なポイントは何ですか?

エルデシュのユニット距離問題は、平面上の n 個の点の間で距離1になるペアの最大数を問う問題。エルデシュはその最大値がほぼ線形（およそ n^{1+o(1)}）になると予想した。

現在知られている最良の一般的な上界は O(n^{4/3})。

エルデシュのユニット距離問題は、平面上の n 個の点の間で距離1になるペアの最大数を問う問題。 エルデシュはその最大値がほぼ線形（およそ n^{1+o(1)}）になると予想した。

離散幾何学で有名な未解決問題の一つが エルデシュのユニット距離問題（Erdős unit distance problem） です。

問いはシンプルです。

平面上に n 個の点を置いたとき、距離がちょうど 1 になる点のペアは最大でいくつ作れるのか？

言い換えると、n 個の点を頂点とし、距離が 1 のペアを辺で結んだ「ユニット距離グラフ」で、辺の本数は最大いくつになるのか、という問題です。

ハンガリーの数学者ポール・エルデシュは、格子状の配置（整数格子）などの例をもとに、最大数は ほぼ線形になるのではないかと予想しました。

その形はおおよそ

n^(1+o(1))

と考えられています。つまり、点の数 n にほぼ比例する増え方になるという予想です。

例えば、正方格子（√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年に提起されて以来、離散幾何学と組合せ幾何学の中心的な未解決問題の一つです。

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