Sylvester–Gallaiの定理
概要
Sylvester–Gallaiの定理（Sylvester–Gallai theorem）とは、実数の平面上の有限個の点が一直線上に並んでいないならば、そのうちちょうど 2 点だけを通る直線（通常直線）が少なくとも 1 本存在する、という定理である。1893 年に Sylvester が問題として出し、Gallai が証明した。点と、その点を通らない結ぶ直線との距離が最小になる組を選ぶと、その直線が通常直線になるという Kelly の短い証明がある。仮定はどれも外せず、一直線上の点、格子点全体のような無限集合、有限体上の平面、複素射影平面の 9 点（Hesse の配置）では通常直線がない。帰結として、一直線上にない $n$ 点を結ぶ直線は少なくとも $n$ 本ある。
前提知識: Euclid平面, 直線, 有限集合, 三平方の定理
縦横に 3 個ずつ、9 個の点を碁盤の目に並べる。このうち 2 点を通る直線を全部引くと 20 本あり、そのうち 3 本の横の列、3 本の縦の列、2 本の対角線の計 8 本は 3 点を通るが、残りの 12 本（たとえば左下の点と、そこから右へ 1、上へ 2 進んだ点を結ぶ直線）はちょうど 2 点しか通らない。三角形の 3 つの頂点、3 辺の中点、重心の 7 点ではどうか。2 点を通る直線は 9 本あり、3 辺と 3 本の中線はどれも 3 点を通るが、2 つの中点を結ぶ 3 本の直線はちょうど 2 点しか通らない。
ちょうど 2 点しか通らない直線をなくすことはできるだろうか。1893 年に Sylvester はこの問いを出題し（Syl93）、約 50 年後に Gallai が「なくすことはできない」ことを証明した（Erd44）。すなわち、平面上の有限個の点が一直線上に並んでいないなら、そのうちちょうど 2 点だけを通る直線が必ず存在する。これが Sylvester–Gallai の定理 である。本記事では、この定理を、点と直線の距離の最小値に着目する Kelly の短い証明（Cox48）で完全に証明し、結論が有限性・実数・「一直線上にない」の各仮定を外すと破れる例、および「$n$ 点は少なくとも $n$ 本の直線を決める」という帰結を述べる。
定理の主張
以下、平面は実数の座標をもつ Euclid平面 $\mathbb{R}^2$ とし、点と点、点と直線の距離はふつうの距離（三平方の定理による）で測る。
$P$ が共線でなければ $P$ は 3 点以上を含む（2 点以下の集合は必ず 1 本の直線上にある）。
平面の有限集合 $P$ が共線でないならば、$P$ の点を結ぶ直線のうちに通常直線が少なくとも 1 本存在する。
$P$ の点を結ぶ直線 $L$ と、$L$ 上にない $P$ の点 $p$ の組 $(p,L)$ 全体を考える。$P$ は共線でないので、$P$ の相異なる 2 点を結ぶ直線 $L$ をとると $L$ 上にない $P$ の点があり、このような組は存在する。$P$ は有限集合なので、結ぶ直線も有限個であり、組も有限個である。そこで、点 $p$ と直線 $L$ の距離 $\operatorname{dist}(p,L)$ が最小となる組 $(p,L)$ を 1 つ選ぶ。$p\notin L$ なので $\operatorname{dist}(p,L)>0$ である。この $L$ が通常直線であることを、背理法で示す。
$L$ が $P$ の点を 3 個以上通るとする。$p$ から $L$ に下ろした垂線の足を $q$ とする（$q$ は $P$ の点とは限らない）。$L$ は $q$ を端点とする 2 本の閉じた半直線の和であり、$L$ 上の $P$ の 3 点はこの 2 本に振り分けられるので、鳩の巣原理により、同じ半直線上に $P$ の相異なる 2 点がある（$q$ 自身が $P$ の点なら両方の半直線に属するとみなしてよい）。同じ半直線上の相異なる 2 点は $q$ からの距離が異なるので、$q$ から遠い方を $a$、近い方を $b$ とする。$|qa|>|qb|\ge0$ なので $a\ne q$ であり、$b$ は線分 $qa$ 上の $a$ と異なる点である（$b=q$ のこともある）。
$p$ と $a$ を結ぶ直線を $M$ とする。$M$ は $P$ の点を結ぶ直線で、$M\ne L$（$p\notin L$）だから $M$ と $L$ の交点は $a$ だけであり、$b\notin M$ である。以下、$\operatorname{dist}(b,M)<\operatorname{dist}(p,L)$ を示す。これが示されれば、組 $(b,M)$ は $\operatorname{dist}(p,L)$ より小さい距離をもち、$(p,L)$ の選び方に反するので、$L$ は通常直線である。
（1）$\operatorname{dist}(q,M)<|pq|$ であること。三角形 $pqa$ は $q$ で直角なので、その面積は $\frac12|pq|\,|qa|$ である。同じ面積を底辺 $pa$ と高さ $\operatorname{dist}(q,M)$ で表すと $\frac12|pa|\operatorname{dist}(q,M)$ なので、
$$\operatorname{dist}(q,M)=\frac{|pq|\,|qa|}{|pa|}$$
である。三平方の定理により $|pa|^2=|pq|^2+|qa|^2>|qa|^2$（$|pq|=\operatorname{dist}(p,L)>0$）なので $|qa|/|pa|<1$ であり、$\operatorname{dist}(q,M)<|pq|$ となる。
（2）$\operatorname{dist}(b,M)\le\operatorname{dist}(q,M)$ であること。$M$ の単位法線ベクトルを $\mathbf{n}$ とすると、点 $x$ と $M$ の距離は $|\mathbf{n}\cdot(x-a)|$ である（$a\in M$）。$b$ は線分 $qa$ 上にあるので、$0< t\le1$ によって $b-a=t(q-a)$ と書ける（$t=|ab|/|aq|$）。よって
$$\operatorname{dist}(b,M)=|\mathbf{n}\cdot(b-a)|=t\,|\mathbf{n}\cdot(q-a)|=t\operatorname{dist}(q,M)\le\operatorname{dist}(q,M)$$
である。
（1）と（2）から $\operatorname{dist}(b,M)<|pq|=\operatorname{dist}(p,L)$ であり、$b\in P$、$b\notin M$ だから $(b,M)$ は考えている組の 1 つである。これは最小性に反する。$\square$
証明のかなめは、「最も近い点と直線の組」を選ぶと、直線上に 3 点があるならもっと近い組が作れるという点にある。この証明は Kelly によるもので、Coxeter の論文で紹介された（Cox48）。証明は距離と、直線上の点の並び（半直線）を使っており、この 2 つが定理の成立に本質的であることは、ex-sylvester-gallai-theorem-complex と ex-sylvester-gallai-theorem-finite-field が示す。
例と反例
- 冒頭の $3\times3$ の碁盤の目 $P=\{0,1,2\}^2$ では、結ぶ直線は 20 本で、3 点を通るものが 8 本、通常直線が 12 本である。9 点から 2 点を選ぶ組は $\binom92=36$ 組で、3 点を通る直線は 3 組ずつ、通常直線は 1 組ずつを受けもつので $8\cdot3+12\cdot1=36$ と合う。
- 三角形の頂点 $A,B,C$、辺の中点 $D,E,F$、重心 $G$ の 7 点では、結ぶ直線は 9 本で、3 辺と 3 本の中線が 3 点ずつを通り、中点どうしを結ぶ 3 本が通常直線である（$6\cdot3+3\cdot1=21=\binom72$）。$n=7$ 点で通常直線が 3 本しかない例であり、通常直線の本数は点の個数よりずっと少なくなりうる。
- 逆に、円周上の $n\ge3$ 点（たとえば正 $n$ 角形の頂点）では、直線と円の交点は高々 2 個なので、結ぶ直線 $\binom n2$ 本がすべて通常直線である。
$P=\{(0,0),(1,0),(3,0),(0,1)\}$ とする。直線 $L:y=0$ は $P$ の 3 点を通り、通常直線ではない。$p=(0,1)$ と $L$ の組をとると $\operatorname{dist}(p,L)=1$ で、垂線の足は $q=(0,0)$ である。$q$ から右の閉じた半直線上に $(1,0)$ と $(3,0)$ があるので、$a=(3,0)$、$b=(1,0)$ とする。$p$ と $a$ を結ぶ直線は $M:x+3y=3$ で、
$$\operatorname{dist}(q,M)=\frac{3}{\sqrt{10}}=\frac{|pq|\,|qa|}{|pa|},\qquad\operatorname{dist}(b,M)=\frac{|1-3|}{\sqrt{10}}=\frac{2}{\sqrt{10}}=0.632\ldots<1$$
である（$t=|ab|/|aq|=2/3$）。こうして $(p,L)$ より近い組 $(b,M)$ が得られる。実際 $M$ は $P$ のうち $(0,1)$ と $(3,0)$ しか通らない通常直線である。この $P$ の結ぶ直線は 4 本（$y=0$、$x=0$、$x+y=1$、$x+3y=3$）で、点と直線の組 7 通りの距離を比べると、最小は $(1,0)$ と $x+3y=3$ の組の $2/\sqrt{10}$ である。prf-sylvester-gallai-theorem のとおり、最小の組の直線は通常直線になっている。
$P$ が 1 本の直線上の 3 個以上の点なら、結ぶ直線はその 1 本だけで、$P$ のすべての点を通るので通常直線はない。この例は「共線でない」という仮定を破っており、その仮定が外せないことを示す。
格子点 全体 $\mathbb{Z}^2$ は共線でないが、通常直線をもたない。実際、相異なる $p,q\in\mathbb{Z}^2$ を通る直線は、すべての整数 $t$ に対する点 $p+t(q-p)\in\mathbb{Z}^2$ を通るので、$\mathbb{Z}^2$ の点を無限個通る。満たさない仮定は「$P$ が有限集合である」ことである。証明では、有限性は距離の最小値をとる組の存在に使われていた。
3 元の有限体 $\mathbb{F}_3=\{0,1,2\}$ の上の平面 $\mathbb{F}_3^2$ の 9 点を考え、直線を $\{p+tv\mid t\in\mathbb{F}_3\}$（$p\in\mathbb{F}_3^2$、$v\ne0$）で定める。相異なる 2 点 $p,q$ を通る直線は $\{p+t(q-p)\mid t\in\mathbb{F}_3\}$ ただ 1 本で、ちょうど 3 点からなる。したがって 9 点は共線でない（直線は 3 点しか含まない）のに、どの 2 点を結ぶ直線も 3 点目を通り、通常直線はない。$\mathbb{R}^2$ と違って $\mathbb{F}_3^2$ には距離も点の並びの順序もなく、Kelly の証明は使えない。満たさない仮定は「平面が実数の平面である」ことである。
$\omega:=e^{2\pi i/3}$ とし、複素数を座標とする射影平面 $\mathbb{P}^2(\mathbb{C})$ の 9 点
$$a_k:=[0:1:-\omega^k],\qquad b_k:=[-\omega^k:0:1],\qquad c_k:=[1:-\omega^k:0]\qquad(k=0,1,2)$$
を考える（3 次曲線 $x^3+y^3+z^3=0$ の変曲点として知られる Hesse の配置）。$\mathbb{P}^2(\mathbb{C})$ の 3 点が 1 本の直線上にあることは、それらの斉次座標を並べた 3 次正方行列の行列式が $0$ であることと同値である。
$a_0,a_1,a_2$ はすべて直線 $x=0$ 上にあり、$b$ の 3 点は $y=0$ 上、$c$ の 3 点は $z=0$ 上にある。$a$ の点、$b$ の点、$c$ の点を 1 つずつとると
$$\det\begin{pmatrix}0&1&-\omega^i\\-\omega^j&0&1\\1&-\omega^k&0\end{pmatrix}=1-\omega^{i+j+k}$$
であり、これが $0$ になるのは $i+j+k$ が $3$ の倍数のときである。したがって $a_i$ と $b_j$ を結ぶ直線は、$i+j+k\equiv0\pmod3$ となるただ 1 つの $k$ について $c_k$ を通る。$a_i,c_k$ や $b_j,c_k$ を結ぶ直線についても同様である。9 点はすべて $xyz=0$ 上にあり、座標軸の直線でない直線は $x=0$、$y=0$、$z=0$ とそれぞれ 1 点でしか交わらないので、9 点のうち 3 点より多くは通らない。以上から、9 点のどの 2 点を結ぶ直線もちょうど 3 点を通り、通常直線はない。9 点は共線でない（たとえば $a_0,a_1,b_0$ は $a$ の 2 点を通る直線 $x=0$ に $b_0$ がないので共線でない）。直線 $x+2y+4z=0$ はこの 9 点のどれも通らないので、これを無限遠直線とみなせば、$\mathbb{C}^2$ の 9 点で同じ性質をもつものが得られる。満たさない仮定は「座標が実数である」ことであり、Sylvester–Gallai の定理は実数の順序と距離に依存している。
帰結と補足
$n\ge3$ 個の点からなる平面の有限集合 $P$ が共線でないならば、$P$ の点を結ぶ直線は少なくとも $n$ 本ある。
$n$ についての数学的帰納法で示す。$n=3$ なら $P$ は三角形の 3 頂点で、結ぶ直線は 3 本である。$n\ge4$ とし、$n-1$ 点では主張が成り立つとする。thm-sylvester-gallai-theorem により、$P$ のちょうど 2 点 $p,q$ だけを通る通常直線 $L_0$ がある。$P':=P\setminus\{p\}$ とおく。
$P'$ が共線なら、$P'$ の $n-1$ 点はある直線 $L$ 上にあり、$P$ は共線でないので $p\notin L$ である。このとき $L$ と、$p$ と $P'$ の各点を結ぶ $n-1$ 本の直線は、どれも相異なる（$p$ を通る直線は $L$ と 1 点でしか交わらないので、$p$ と $P'$ の異なる点を結ぶ直線は異なり、また $L$ とも異なる）ので、結ぶ直線は少なくとも $n$ 本ある。
$P'$ が共線でないなら、帰納法の仮定により $P'$ の点を結ぶ直線は $n-1$ 本以上あり、それらはどれも $P$ の点を結ぶ直線でもある。一方 $L_0$ は $P$ の点のうち $p,q$ しか通らないので、$P'$ の点は $q$ しか通らず、$P'$ の点を結ぶ直線ではない。よって $P$ の点を結ぶ直線は $(n-1)+1=n$ 本以上ある。$\square$
$n$ 本ちょうどになる例として、1 本の直線上の $n-1$ 点とその直線上にない 1 点がある。この結果は de Bruijn と Erdős によるより一般の定理の特別な場合である（dBE48）。
$\mathbb{R}^k$（$k\ge2$）の有限集合で、すべての点が 1 本の直線上にあるのでなければ、やはり通常直線がある。prf-sylvester-gallai-theorem の議論は、組 $(p,L)$ を選んだ後は $p$ と $L$ を含む平面の中だけで行われる（$q$、$a$、$b$、$M$ はすべてその平面にある）ので、そのまま通用する。
Sylvester の問題は 1893 年に Educational Times に出題され（Syl93）、1943 年に Erdős が改めて American Mathematical Monthly に出題し（Problem 4065、Monthly 50, p. 65）、翌年、Gallai の解（旧姓 Grünwald 名義）を含む解答が掲載された（Erd44）。本記事の証明は Kelly によるもので、Coxeter が 1948 年に紹介した（Cox48）。AZ18 の Chapter 11 も Kelly の証明と cor-sylvester-gallai-theorem-lines を扱っている。
通常直線は 1 本より多く存在する。共線でない $n$ 点が決める通常直線の本数の下界は、Kelly–Moser の $3n/7$、Csima–Sawyer の $6n/13$（$n\ne7$）と改良されてきた。Green と Tao は、$n$ が十分大きければ通常直線が少なくとも $n/2$ 本あること（Dirac と Motzkin の予想）を証明した（GT13。同論文にこれらの経緯もまとめられている）。ex-sylvester-gallai-theorem-examples の 7 点は通常直線が 3 本で、$3n/7$ の下界がちょうど達成される例である。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
