未解決問題、幾何学, 組合せ論と離散数学、1946年に提起

エルデシュの単位距離問題

未解決エルデシュ

平面 $\mathbb{R}^2$ 内の任意の $n$ 個の点からなる集合において、ユークリッド距離が $1$ である点の対の最大数 $u(n)$ の漸近的な増大度を決定せよ。

提起者, 1946ポール・エルデシュ

研究の最前線 2026年時点

2026年時点で、ユークリッド平面における $u(n)$ の正確な漸近指数は依然として未解決であるが、2026年5月に状況は劇的に変化した。80年間にわたり最良の下界はエルデシュが1946年に整数格子から導いた $n^{1+c/\log\log n}$ であり、エルデシュは $u(n) = n^{1+o(1)}$ と予想していた。2026年5月、AIが発見した代数体による構成（アロンらのプレプリントで検証され、サウィンにより改良）がこの予想を覆し、 $u(n) = \Omega(n^{1.014})$ を確立したことで、真の増大度は $n^1$ を真に上回るべき乗と、1984年のスペンサー–セメレディ–トロッターの上界 $O(n^{4/3})$ の間に絞られた。

既知の最良の結果

最良の一般上界は、スペンサー、セメレディ、トロッター（1984年）によって証明された $u(n) = O(n^{4/3})$ である。
任意に大きい $n$ に対する明示的な下界 $u(n) > n^{1.014}$ が2026年に確立され（サウィン、プレプリント。アロンらによって検証されたOpenAIの反例を発展させたもの）、エルデシュの $n^{1+o(1)}$ 予想が反証された。

使われた手法と限界

手法	達成したこと	限界
接続幾何学と交差数不等式（セメレディ–トロッター、セーケイ）	$n$ 個の点と $n$ 個の単位円の間の接続数を評価することで上界 $u(n) = O(n^{4/3})$ を証明した	位相的手法や2部グラフの交差数評価では、ユークリッドの単位円と、実際に $\Theta(n^{4/3})$ の接続数を達成する擬円とを区別できない
代数体とゴロド–シャファレヴィッチ類体塔（アロンら、サウィン）	判別式が小さくノルム $1$ の分解素イデアルを多く持つ高次の代数体から $\mathbb{C} \cong \mathbb{R}^2$ 内の点集合を構成し、 $u(n) > n^{1.014}$ を達成した	サウィンはこの枠組みによる既知の無条件な代数体構成では指数を約 $1.2143$ より大きくできないことを示しており、 $4/3$ との間には依然としてギャップが残る

未解決の問い

ユークリッド平面における真の漸近指数 $\limsup_{n \to \infty} \frac{\log u(n)}{\log n}$ はいくつか。
単位円の代数的剛性を用いて、上界 $O(n^{4/3})$ をある $c > 0$ に対する $O(n^{4/3 - c})$ へと改良できるか。

参考文献

Paul Erdős (1946). On sets of distances of n points · DOI:10.1080/00029890.1946.11991674
Joel Spencer, Endre Szemerédi, William T. Trotter (1984). Unit distances in the Euclidean plane · DOI:10.1007/pl00000428
Noga Alon, Thomas F. Bloom, W. T. Gowers, Daniel Litt, Will Sawin, Arul Shankar, Jacob Tsimerman, Victor Wang, Melanie Matchett Wood (2026). Remarks on the disproof of the unit distance conjecture · arXiv:2605.20695v1 [プレプリント・未査読]
Will Sawin (2026). An explicit lower bound for the unit distance problem · arXiv:2605.20579v1 [プレプリント・未査読]