Erdősの異なる距離問題

同義語:Erdősの相異なる距離問題Erdos distinct distances problemErdős distinct distances problem異なる距離問題相異なる距離問題

概要

Erdősの異なる距離問題(Erdős distinct distances problem)とは、平面の $n$ 個の点の間に現れる相異なる距離の個数の最小値 $g(n)$ の大きさを問う問題である。正方格子から $g(n)\le cn/\sqrt{\log n}$ が得られ、Guth と Katz は平面の運動を 3 次元の直線に読み替えて多項式法で $g(n)\ge cn/\log n$ を示した。$\sqrt{\log n}$ の因子の差が残っている。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 離散幾何学, 交差数(グラフ), Szemerédi–Trotterの定理

Erdősの異なる距離問題(Erdős distinct distances problem)は、平面の $n$ 個の点の間に現れる相異なる距離の個数が最小でいくつになるかを問う問題である。Erdős が 1946 年に提起した(Erd46)。この最小値を $g(n)$ とすると、正方格子から $g(n)\le cn/\sqrt{\log n}$ が得られ(thm-dd-upper)、Guth と Katz が $g(n)\ge cn/\log n$ を示した(GK15、thm-dd-gk)。指数 $1$ は確定したが、$\sqrt{\log n}$ の因子の差が残っている。
この問題は、点と直線の接続の理論(Szemerédi–Trotterの定理)の出発点の一つであり、Guth–Katz の証明は多項式を使う組合せ幾何(多項式法)の代表例である。この記事では、次のことを証明する。

  • 格子の上界が、整数論の評価 1 つから出ること(thm-dd-upper)。
  • 交差数だけで $cn^{4/5}$ の下界が出ること(thm-dd-szekely)。
  • 問題が 3 次元の直線の交わりの問題に帰着すること(prf-dd-gk)。
    3 次元の直線についての 2 つの定理(thm-dd-incidence)は証明しない。その筋だけを述べる。

問題

相異なる距離の最小個数

$n\ge2$ 個の点からなる平面の集合 $P$ について $\Delta(P):=\{\lvert x-y\rvert\mid x,y\in P,\ x\neq y\}$ とおく。$\lvert\Delta(P)\rvert$ の、$\lvert P\rvert=n$ である $P$ についての最小値を $g(n)$ と書く。

$P'\subset P$ なら $\Delta(P')\subset\Delta(P)$ なので、$g$ は広義増加である。

小さい $n$ と規則的な配置
  • $g(3)=1$:正三角形。
  • $g(4)=g(5)=2$(Erd46 §1):上界は正五角形とその 4 頂点である。$g(4)\ge2$ は次のように分かる。距離が 1 種類だとすると、4 点のうち 3 点は一辺 $r$ の正三角形 $ABC$ をなし、第 4 の点は $A,B$ を中心とする半径 $r$ の 2 円の交点で $C$ と異なる。それは $C$ を辺 $AB$ で折り返した点で、$C$ との距離は $\sqrt3r\ne r$ である。
  • $g(7)\le3$:正六角形とその中心。一辺を $1$ とすると距離は $1,\sqrt3,2$ である。
  • 等間隔に一直線に並べると $n-1$ 種類、正 $n$ 角形では $\lfloor n/2\rfloor$ 種類である。

$n$ が大きいとき、直線上や円周上より格子の方が距離の種類が少ない。

格子による上界

定数 $c>0$ があり、すべての $n\ge2$ について $g(n)\le cn/\sqrt{\log n}$ である。

$m:=\lceil\sqrt n\rceil$ とし、$\{0,\dots,m-1\}^2$ から $n$ 点を選ぶ。距離の 2 乗は $u^2+v^2$($0\le u,v< m$)の形の正の整数で、$2m^2$ 以下である。$x$ 以下の正の整数のうち 2 つの平方の和で書けるものの個数は $Cx/\sqrt{\log x}$ 以下である(Landau の定理。この記事では証明しない)。$x=2m^2\le 2(\sqrt n+1)^2$ とすれば結論を得る。$\square$

これは Erd46 Theorem 1 の後半である。Erdős は $g(n)\ge\sqrt{n-3/4}-1/2$ も同じ定理で示した(証明は 離散幾何学)。

下界の歩み

Sze97 と GK15 §1 の紹介にしたがって下界を並べる。

下界人方法
$n^{1/2}$Erdős(1946)凸包の頂点の周りの半円
$n^{2/3}$Moser(1952)—
$n^{5/7}$Chung(1984)—
$n^{4/5}/(\log n)^{c}$Chung–Szemerédi–Trotter(1992)—
$cn^{4/5}$Székely(1997)交差数(thm-dd-szekely)
$n^{(48-14e)/(55-16e)-\varepsilon}$Katz–Tardos指数はおよそ $0.8641$
$cn/\log n$Guth–Katz(2015)多項式法(thm-dd-gk)

Székely と Katz–Tardos の間に Solymosi–Tóth、Tardos の改良がある。
$n^{2/3}$ には、単位距離グラフ の上界 $u(n)\le Cn^{4/3}$ を使う短い道もある。距離ごとに組を分けると $g(n)\,u(n)\ge\binom n2$ となるからである(Erdősの問題)。

1 点から見た距離

Székely の定理は 1 点から測った距離の個数についての主張で、次の節の定理より弱いが、thm-dd-gk の結論からは従わない形をしている。
証明には、重複辺のあるグラフの交差数の下界を使う。

多重グラフの交差数の下界

定数 $c>0$ があり、$n$ 頂点、$e$ 辺、辺の重複度の最大値が $m$ の多重グラフ $G$ は、$e\le5nm$ であるか $\operatorname{cr}(G)\ge ce^3/(n^2m)$ を満たす。

証明の所在

多重グラフの交差数も、交差数(グラフ) の良い描画と同じく、描画の交差の個数の最小値である。主張は Sze97 Theorem 7 である(重複度で辺を分けて交差数補題を当て、Hölder の不等式でまとめる。この記事では証明しない)。$m=1$ が 交差数(グラフ) の定理「交差数補題」にあたる。

これを使って次を示す(Sze97 Theorem 11)。

1 点から測った距離

定数 $c>0$ があり、$n\ge2$ について、平面の $n$ 点の集合 $P$ のある点からほかの点までの距離は $cn^{4/5}$ 種類以上ある。とくに $g(n)\ge cn^{4/5}$ である。

円弧のグラフと対称軸

$t$ を、$P$ の点から測った距離の種類の最大値とする。$\varepsilon>0$ を後で決める小さい定数として $t\le\varepsilon n/\log n$ としてよい(そうでなければ $n$ が大きいとき $t\ge n^{4/5}$ である。$n$ が小さいときは $c$ を小さくとればよい)。
グラフ. 各 $p\in P$ と $p$ から測った各距離 $r$ について、$p$ を中心とする半径 $r$ の円を描く。$P$ の点を 3 個以上含む円だけを残し、円周上で隣り合う 2 点を円弧で結ぶ。こうして $P$ を頂点とする多重グラフ $G$ ができる。$p$ の周りの円の上の点は重複を込めて $n-1$ 個で、捨てた円の上の点は $2t$ 個以下なので、$G$ の辺は $n(n-1-2t)\ge n^2/2$ 本以上ある。
対称軸. 円弧 $a$ の両端を $u,v$、中心を $p$ とする。$a$ は $u,v$ の垂直二等分線 $f$ について対称で、$p\in f$ である。逆に直線 $f$ と $f$ の上の点 $p$ と $p$ を中心とする円について、この円の弧で $f$ を対称軸とするものは、$f$ と円の 2 交点のどちらかを内部に含むので、$G$ の辺としては 2 本以下である。よって、$P$ の点を $j$ 個含む直線を対称軸とする $G$ の辺は $2tj$ 本以下である。
$k\ge2$ について、$P$ の点を $k$ 個以上含む直線 $f$ と、$f$ を対称軸とする $G$ の辺 $a$ の組の個数を $X_k$ とする。Szemerédi–Trotterの定理 の系「多くの点を含む直線と多くの直線が通る点」により、$2^i$ 個以上の点を含む直線は $C(n^2/2^{3i}+n/2^i)$ 本以下である。$2^i\le j< 2^{i+1}$ で分けて足すと
$$ X_k\le\sum_{i:\ 2^{i+1}>k,\ 2^i\le n}C\Bigl(\frac{n^2}{2^{3i}}+\frac n{2^i}\Bigr)\cdot2t\cdot2^{i+1}\le C'\Bigl(\frac{tn^2}{k^2}+tn\log n\Bigr) $$
である。
重複度を下げる. $u,v$ を結ぶ辺が $k$ 本以上あるとする。その円弧の中心はどれも $u,v$ の垂直二等分線 $f$ の上にある。残した円は 3 点以上を含むので、1 つの円から $u,v$ を結ぶ辺は 1 本しかできない。よって $f$ は $P$ の点を $k$ 個以上含み、これらの辺はすべて $X_k$ に数えられる。
$k:=\lceil K\sqrt t\,\rceil$ とする。重複度が $k$ 以上の組を結ぶ辺をすべて除くと、除いた辺は $C'(n^2/K^2+tn\log n)$ 本以下である。$K$ を大きく、$\varepsilon$ を小さくとれば($t\log n\le\varepsilon n$ である)これは $n^2/4$ 以下で、$n^2/4$ 本以上の辺をもち重複度が $k$ 未満の多重グラフ $G_1$ が残る。
交差. 円は $nt$ 個以下で、相異なる 2 円の共有点は 2 個以下、同じ円の弧は内部で交わらないので、円弧の描画の交差は $2\binom{nt}2\le n^2t^2$ 個以下である。端点を共有する 2 弧がもう 1 点で交わるときは、共有する端点から交点までの部分を入れ替えて交点で少しずらすと交差が減る(交差数(グラフ) の良い描画に合わせる標準の操作)。よって $\operatorname{cr}(G_1)\le n^2t^2$ である。
$n$ が大きいとき $n^2/4>5nk$ なので、thm-dd-multi から
$$ n^2t^2\ge\operatorname{cr}(G_1)\ge\frac{c(n^2/4)^3}{n^2K\sqrt t}\cdot\frac12 $$
を得る。整理すると $t^{5/2}\ge c''n^2$、すなわち $t\ge c'''n^{4/5}$ である。$\square$

Guth–Katz の定理

主定理は $g(n)\ge cn/\log n$ である(GK15 Theorem 1.1)。証明は大きく 3 つの部分からなる。距離の問題を四つ組の個数に読み替える部分、四つ組を平面の運動群の中の交わりに読み替える部分(ここまで Elekes–Sharir の枠組み)、その交わりを 3 次元の直線の問題として解く部分である。最後の部分が次の定理で、ここでは主張だけを引く。

3 次元の直線の交わり

$\mathbb{R}^3$ の $N^2$ 本の直線の集合 $\mathcal{L}$ で、どの平面にも $N$ 本以下しか含まれないものを考える。

  1. どの 2 次線織面(2 通りの直線族で覆われる 2 次曲面、regulus)にも $AN$ 本以下しか含まれないなら、$\mathcal{L}$ の 2 本以上が交わる点は $C_AN^3$ 個以下である。
  2. $3\le k\le N$ とすると、$\mathcal{L}$ の $k$ 本以上 $2k$ 本未満が交わる点は $CN^3/k^2$ 個以下である。
    この記事では証明しない(GK15 §2 で主張を述べ、以後の節で証明している)。
Guth–Katz の定理

定数 $c>0$ があり、すべての $n\ge2$ について $g(n)\ge cn/\log n$ である。

四つ組と平面の運動

$P$ を $N$ 点の集合とし、$D:=\lvert\Delta(P)\rvert$ とおく。
段 1:四つ組. $Q$ を $p_1\ne p_2$、$\lvert p_1-p_2\rvert=\lvert p_3-p_4\rvert$ を満たす $(p_1,p_2,p_3,p_4)\in P^4$ の全体とする。距離 $d_i$($1\le i\le D$)をもつ順序対の個数を $n_i$ とすると、$\sum n_i=N(N-1)$、$\lvert Q\rvert=\sum n_i^2$ である。Cauchy–Schwarzの不等式 から
$$ D\ge\frac{N^2(N-1)^2}{\lvert Q\rvert} $$
である。この式を不等式 A と呼ぶ。よって $\lvert Q\rvert\le CN^3\log N$ を示せばよい。
段 2:平面の運動. $G$ を向きを保つ平面の等長変換の群とする。$(p_1,\dots,p_4)\in Q$ に対し、$g(p_1)=p_3$、$g(p_2)=p_4$ となる $g\in G$ がただ 1 つある。$g\in G$ について $m(g):=\lvert P\cap g^{-1}(P)\rvert$ とおく。$Q$ の元は $g$ と $P\cap g^{-1}(P)$ の相異なる 2 点の順序対で定まるので
$$ \lvert Q\rvert=\sum_{g\in G}m(g)\bigl(m(g)-1\bigr) $$
である。この式を等式 B と呼ぶ。平行移動から来る四つ組は $p_3-p_1=p_4-p_2$ を満たし、3 点で第 4 の点が決まるので $N^3$ 個以下である。
段 3:直線. 平行移動でない $g\in G$ は、不動点 $O$ と回転角 $\theta\in(0,2\pi)$ でただ 1 通りに定まる。$\Phi(g):=(O,\cot(\theta/2))\in\mathbb{R}^3$ とおくと、$\Phi$ は単射で、全射でもある。$p,q\in P$ について $g(p)=q$ となる平行移動でない $g$ の全体の像を $\ell_{pq}$ とする。$J$ を $+90^\circ$ の回転とすると
$$ \ell_{pq}=\Bigl\{\Bigl(\frac{p+q}2+\frac s2J(q-p),\ s\Bigr)\ \Big|\ s\in\mathbb{R}\Bigr\} $$
である。この直線の式を式 C と呼ぶ。実際、$p=q$ なら $O=p$ で明らかである。$p\ne q$ なら $O$ は $p,q$ の垂直二等分線の上にあるので、$w=q-p$ として $O=\frac{p+q}2+\frac s2Jw$ と書ける。$q-O=\frac w2-\frac s2Jw$ が $p-O=-\frac w2-\frac s2Jw$ の $\theta$ 回転に等しいという条件の $Jw$ 成分は $-\frac s2\cos\theta-\frac12\sin\theta=-\frac s2$、すなわち $s(1-\cos\theta)=\sin\theta$ で、これは $s=\cot\frac\theta2$ と同値である。このとき $w$ 成分の条件 $s\sin\theta=1+\cos\theta$ も成り立つ。よって $\ell_{pq}$ は直線で、$\mathcal{L}:=\{\ell_{pq}\mid p,q\in P\}$ は $N^2$ 本からなる($p$ の像と $p'$ の像を決める運動は 1 つ以下なので相異なる)。$m(g)$ は $\Phi(g)$ を通る $\mathcal{L}$ の直線の本数である。
段 4:一般の位置. $p$ を固定する。$\ell_{pq},\ell_{pq'}$($q\ne q'$)に共通点はなく($g(p)$ は 1 つである)、式 C から方向が異なるので、ねじれの位置にある。よって同じ $p$ の直線は、1 点を共有することも同じ平面に乗ることもない。したがって 1 点を通る $\mathcal{L}$ の直線も、1 平面に含まれる直線も $N$ 本以下である。1 つの 2 次線織面に含まれる直線が $AN$ 本以下であることも示される(GK15 §2)。
段 5:足し合わせ. 等式 B の和のうち平行移動でない部分を、$m(g)$ が $2^j$ 以上 $2^{j+1}$ 未満かどうかで分ける。$m(g)\le N$ なので $j\le\log_2N$ である。$j=1$ は thm-dd-incidence の 1 により $4^2C_AN^3$ 以下、$j\ge2$ は 2 により $4^{j+1}\cdot CN^3/4^j=4CN^3$ 以下である。よって $\lvert Q\rvert\le N^3+C'N^3\log N$ であり、不等式 A から $D\ge cN/\log N$ を得る。$\square$

不等式 A を格子に当てると、この方法の限界が少し見える。thm-dd-upper の格子では $D\le cN/\sqrt{\log N}$ なので、不等式 A から $\lvert Q\rvert\ge c'N^3\sqrt{\log N}$ である。したがって $\lvert Q\rvert\le CN^3$ のような評価は成り立たない。四つ組の個数の評価だけでは、$\log$ の因子を完全には除けない。

直線の定理の証明の筋

thm-dd-incidence は、低い次数の多項式の零点集合に直線を押し込むことで証明される(GK15 §3〜§4)。交わる直線の本数で手法が分かれる。
$k\ge3$:セル分割. 多項式のハムサンドイッチ定理(Stone–Tukey)を点の集合に繰り返し当てると、次数 $d$ の多項式 $p$ で、$\mathbb{R}^3\setminus\{p=0\}$ の各セルに点が高々 $C\lvert S\rvert/d^3$ 個しかないものが得られる($S$ は点の集合)。直線は零点集合に含まれない限り $d$ 個以下の点でしか零点集合と交わらないので、高々 $d+1$ 個のセルを通る。点の多くがセルの内部にあれば、セルごとの素朴な評価を足すだけで評価が得られる。そうでなければ点の多くは低い次数の曲面の上にあり、代数的な議論に進む。
$k=2$:flecnode 多項式. 2 本の交点では 3 本の交点のような特異性が使えない。そこで Salmon の flecnode 多項式を使う。次数 $d$ の曲面 $p=0$ について、直線が 3 次まで接する点で消える次数 $11d-24$ の多項式 $\operatorname{Fl}(p)$ があり、曲面が線織面であることと $\operatorname{Fl}(p)$ が曲面上で消えることは同値である。$p$ と $\operatorname{Fl}(p)$ がともに $d(11d-24)$ 本を超える直線の上で消えれば、Bézout 型の補題により共通因子をもつので、$p$ は線織面の因子をもつ。平面でも 2 次線織面でもない線織面では、母線どうしの交わりが少ないので、交点の個数が評価できる。thm-dd-incidence の 1 で平面と 2 次線織面の本数を制限するのはこのためである。

反例の表

外す条件反例成り立たなくなるもの
Euclid の距離$\ell^\infty$ の距離で $\{1,\dots,m\}^2$。距離は $1,\dots,m-1$$n=m^2$ 点で $\sqrt n-1$ 種類なので、thm-dd-gk の結論が偽
実数体$\mathbb{F}_q^2$(有限体)の全体で $x^2+y^2$ を距離の 2 乗とする$n=q^2$ 点で値は $q$ 個以下なので、結論が偽
実数体$\mathbb{C}^2$ の直線 $\{(z,iz)\}$ の上の $n$ 点で $(x-x')^2+(y-y')^2$ を測る値はすべて $0$ で 1 種類
平面$\mathbb{R}^k$($k\ge3$)の $\{1,\dots,m\}^k$$n=m^k$ 点で距離の 2 乗は $km^2$ 以下なので、$kn^{2/k}$ 種類以下で結論が偽(Erd46 §1)

第 2 行の有限体では、thm-dd-incidence に相当する主張も偽である(GK15 §4)。第 3 行は、平方和が $0$ になる方向があることが効いている。実数の平面では円周の点の並びと順序が prf-dd-szekely の交差の議論を支えており、Guth–Katz の証明もセル分割に実数の順序を使う。

残された問題

$g(n)$ について分かっているのは $cn/\log n\le g(n)\le c'n/\sqrt{\log n}$ である。Erdős は上界が正しい大きさであると予想した。Blo26 の問題 89(2026 年 1 月の更新)はこれを未解決と記載し、より強い形として、ある 1 点から $cn/\sqrt{\log n}$ 種類の距離が見えるかという問いを挙げている。
Guth–Katz の証明は四つ組全体を数えるので、thm-dd-szekely のような 1 点についての情報を与えない。

関連項目

参考文献

[1]
P. Erdős, On sets of distances of n points, The American Mathematical Monthly, 1946, pp. 248–250、§1、Theorem 1
[2]
Larry Guth, Nets Hawk Katz, On the Erdős distinct distances problem in the plane, Annals of Mathematics, 2015, pp. 155–190、Theorem 1.1、§1〜§4(節番号は arXiv:1011.4105v1)
[3]
László A. Székely, Crossing numbers and hard Erdős problems in discrete geometry, Combinatorics, Probability and Computing, 1997, pp. 353–358、Theorem 7、Theorem 11(定理番号は著者公開稿)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する