四色定理

数学 四色問題

　最近数学に凝っていて，いろいろ読んでいる。もちろん専門の本ではなくて，素人向けの啓蒙書ばかりだが，とても勉強になる。今読んでるのは「数学ガール」という異色の数学本。高二の「僕」が同級下級の美少女たちとちょっと背伸びした数学を学んでいくという，到底あり得ないハズカシイ設定の萌える数学読本だが，数学の内容は分かりやすくてなかなかよい。
　数学でも特に興味深いのが，証明も反証もされていないが，正しいと予想されている未解決問題だ。現在及び過去の未解決問題の中には，素人にはその内容を理解することが難しいＰ≠ＮＰ問題やリーマン予想，ポアンカレ予想などもあるが，驚くほど簡単なものもある。長い間未解決だったフェルマーの最終定理や，四色問題はその例である。
　四色問題とは，「平面上のいかなる地図も四色で塗り分けられる」という予想である。これが解決され，四色定理となったのは，私が生れた年らしい。ちょっとしたことだが，なんだかこの問題に親しみを覚える。地図の塗り分けのルールは常識的なもので，平面を複数の領域（国）に曲線（国境）で分割したものを考え，国境を共有する国同士は異なる色で塗るというものである。国境線ではなく，点のみを共有する国なら同じ色で塗ってもよい。平面上の地図と言ったが，球面状の地図でもまったく同様である。適当に射影することで，球面上の地図は平面上の地図と同一視できるからだ。
　勝手な地図を描いて実際にやってみると，塗り分けに三色では足りないことはすぐわかる。四色あれば塗り分けられそうだという予測もつく。もちろん塗り分けに四色いらない地図もある。正方形を敷きつめた碁盤目状の地図なら二色で足り，正六角形を敷きつめた地図なら三色で足りる。ただ，どんな地図でも四色で足りることを証明するとなると難しい。四色では足りなくて，五色ないと塗り分けられない地図があるかも知れない。
　四色問題は，1852年にド・モルガンがハミルトンに宛てた書翰で提起され，1976年アッペルとハーケンにより解決された。四色問題をド・モルガン自身が思いついたのではなく，彼の学生ガスリーが兄から聞いた問題としてド・モルガンに質問したのが発端だ。ガスリーより前に，どんな地図でも四色で塗り分け可能という事実が地図製作業者の間で知られていたという説があるが，これは怪しいらしい。地図を描くのにそんなに色を節約する必要はないし，湖や海を青で塗るとか，飛び地も本国と同じ色で塗るという縛りがあるので，四色問題が出てくるわけではないということだ。
　でも，地図製作業者も興味本位で色をとことん節約してみようとか考えたかもしれないよな…。まあ，地図業者間で四色問題が知られていたという事実を確認できる史料は見あたらないのだろう。今も昔も，実務に携わる人の発想や対話はなかなかきちんとした記録に残らない。史料がないからといって絶対にないとはもちろん言えないのだが，これは仕方がない。歴史はそうやって作るしかなく，四色問題発見の栄誉は，幸運にもそれを証明する記録が残った最先の人であるガスリー兄に与えられる。
　四色問題の発見から解決まで，百年以上の時間が費やされたが，この間には数学界に壮大な早とちりがあった。問題発見から間もなく出た誤った証明が，なんと十年にもわたって正しいと信じられていた。1879年のケンペによる証明の不備が，1890年ヒーウッドによって指摘されるまで，四色問題は解決されたと誤解されていたのだ。今でこそ，数学の未解決問題の証明は，しばしば数年にわたる他の数学者の徹底的な検証が経たうえでなければ，証明として認められないが，百年前は結構ザルだったのか？あるいは当時はまだ四色問題の歴史も浅く，それほどの難問と思われてなくて数学者たちが不覚を取ったのかも知れない。いずれにしろ，こういった苦い経験にも学んで数学界は進歩し発展してきた。ケンペの証明の不備を指摘したヒーウッドは，同時に五色定理の証明を示すが，四色問題はなお八十余年にわたって数学者の挑戦を挫き続けた。
　その間，平面・球面とは異なる曲面上の地図の塗り分け問題も考察された。浮き輪やドーナツの表面を（二次元の）トーラスと言うが，その上の地図は七色あれば塗り分けられる。二つ穴のあいた二人乗り浮き輪（種数２のトーラス）だと八色である。ｎ個穴のあいた種数ｎのトーラスに対して何色かについても一般式があり，ヒーウッドが導出した。この一般式は二次不等式を解くことで得られ，根号（√）の入った不思議な式だ。ヒーウッドが導いた数は何色で足りるかを示すだけで，本当にそれだけの色数が必要かについては未確認だったのだが，ヒーウッドの数が必要十分であることも示された。四色定理の証明に先立つこと八年，ヤングとリンゲルの仕事である。
　結局，四色定理の証明は，コンピュータで厖大な計算をしてようやく達成される。トーラス上の地図の塗り分けについては，何色が必要十分か，紙とペンで計算できたのに，平面・球面上の地図ではそうはいかなかったのだ。より単純な問題がより難しいのは不思議な話で，多次元のポアンカレ予想が三次元のそれより容易に証明されたこととどこか似ている。ともあれ，アッペルとハーケンは当時のコンピュータを千時間以上も動かして四色定理の証明に漕ぎつけた。これには不快感を示す数学者も多かったらしく，数学で理想とされるエレガントな証明に対して，エレファントな証明と揶揄されたりする。その後証明法は多少スリム化されはするが，コンピュータを使わない四色定理の証明は未だに知られていない。
　四色問題にアタックするのに，いろいろな方法が試みられたが，結局しらみつぶしに調べてゆくという泥臭い方法しか解決につながらなかった。平面上のあらゆる地図を，有限個の部分パターン（国々の配置）に還元して考えるのだが，有限個の配置といってもとても多く，その一つ一つの配置の検証にも実に多くの計算が必要だった。そのためコンピュータが不可欠だったのだ。具体的には，「可約配置の不可避集合」というのをつくる。
　仮に四色塗り分け予想が間違っていれば，五色以上なければ塗り分けられない地図が存在する。そのような地図のうち，最小のもの，すなわち最も国の数が少ない地図を「最小反例」という。そして最小反例には絶対に含まれない国々の配置を，「可約配置」と呼ぶ。一方，「不可避集合」というのは，国々の配置を要素とする有限集合で，どんな地図でもこの集合の要素を少なくとも一つは含むような集合である。もし，可約配置だけを要素とする不可避集合が存在すれば，四色定理が証明されたことになる。最小反例に決して含まれない可約配置がどんな地図にも不可避的に含まれるとすれば，最小反例は存在できないからである。アッペルとハーケンは，二千程度の可約配置からなる不可避集合を構築したのである。コンピュータは，個々の配置が可約配置であるか否かを判定するのに欠かせなかった。