シルべスター・ガライの定理

この記事は非公開化されました。

integers.hatenablog.com

非公開前の内容要約: Sylvester-Gallaiの定理とKellyによるその証明について。

一時復元

シルべスター・ガライの定理

Sylvesterの問題 (1893年)
平面上の点からなる有限集合 $S$ について、 $S$ の2点を結んで出来る任意の直線が $S$ の3点を通るという条件を満たすとき $S$ の点は全て同一直線上にあるといえるか？

この問題は肯定的に解決されており、Sylvester-Gallaiの定理と呼ばれています。

集合 $S$ に対して、 $S$ の2点のみを通るような直線のことを通常直線と言います。この言葉を用いればSylvester-Gallaiの定理は「 $S$ の点が同一直線上になければ通常直線が少なくとも一つは存在する」となります。

歴史的にはMelchiorが1941年に射影双対版を証明しており、Erdősがそれに気づかずに1943年に再度問題として提出し、Gallaiがそれに解答を与えました。
その後、1944年から1948年の間*1にKellyという人が最もシンプルな証明を発見しています。

Sylvester-Gallaiの定理は有名な定理で、一般化や類似の定理の研究が多数なされています。2013年にはGreenとTaoが次の定理を証明しています:

定理 (Green-Tao)
$n$ が十分大きいとき、平面内の同一直線上にはない $n$ 点集合 $S$ に関する通常直線の数は $n/2$ 以上である。

ちなみに、

山中伸弥、益川敏秀著『「大発見」の思考法』文春新書

において益川先生がこの問題について書いておられます。要約すると、名古屋大学二年の時に数学コンクールがあってその中にこの問題があった(有名問題であったことはどうやら知らなかったらしい)。そしてこの問題だけは誰も解けずに後で解答(Kellyの証明)を聴いてその簡単さ(と自分で気づかなかったこと)に腹が立ったというエピソードです。

益川先生はこれに気づかなくて腹が立ったということですが、実際の歴史では問題が提出されてから50年以上もたってから発見された証明なのです。未解決問題であっても証明が難しいとは限らないという例で時々引き合いに出される問題でもあります*2。

KellyによるSylvester-Gallaiの定理の証明

集合 $S$ を平面内の点の有限集合であって、全体が同一直線上にあるようなものではないとする。 $S$ の2点を結んで出来る直線全体の集合を $L$ とおく。このとき、

$\mathcal{D} :=\{ d(\ell, P) \mid \ell \in L, \ P \in S\setminus \ell \}$

を考える。ここで、 $d(\ell, P)$ は $\ell$ と $P$ の距離を表す。同一直線上にないという仮定から $\mathcal{D} \neq \emptyset$ であり、明らかに有限集合である。よって、 $\mathcal{D}$ には最小元が存在する。その最小元を実現するような直線 $\ell$ と点 $P$ を考える。この $\ell$ が実は通常直線である。それは次のように背理法で証明できる。
f:id:integers:20160123054132p:plain
図において $P$ から $\ell$ に下ろした垂線の足を $Q$ とする( $S$ の元というわけではない)。 $\ell$ 上に $S$ の3点が乗っていると仮定する。このとき、少なくとも2点は $Q$ に関して同じ側にある。それらを図のように $P_1, P_2$ とする( $Q$ と一致してもかまわない)。 $P$ と $P_2$ を通る直線を $\ell' \in L$ とすると $\ell'$ と $P_1$ の距離は $\ell$ と $P$ の距離より小さい。これは最小性に反する。 Q.E.D.