インテジャーズ

インテジャーズ

数、特に整数に関する記事。

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

3

3という数を見ると次の組合せ幾何に関するSylvesterの問題を思い出します:

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.

*1:正確な発見年は知りません。

*2:何故か日本語のWikipedia記事はありません。