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

平面上の点と「距離1」の最大数

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

問いはシンプルです。

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

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

エルデシュの予想

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

その形はおおよそ

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

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

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

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

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

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

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