どくしょ絵日記

面白かった本を紹介します(お絵かき付き)

Four Colors Suffice

 

Four Colors Suffice: How the Map Problem Was Solved: Revised Color Edition (Princeton Science Library)

Four Colors Suffice: How the Map Problem Was Solved: Revised Color Edition (Princeton Science Library)

 

邦訳はこちら  四色問題 (新潮文庫)

4色問題である。その証明が、現代的な論争を引き起こしたという経緯があり、関心を持っていたトピックだ。「これは、証明なのか」「そもそも証明って何だ」という内省を数学者の間に引き起こしたというから、穏やかでない。

「これは、〇〇なのか」といった物議でまっさきに頭に浮かぶのは、1917年、マルセル・デュシャンがトイレを美術展覧会へ出品した事件ではないだろうか(作品名「泉」)。トイレは芸術なのだろうか?

この出来事は、嫌悪と賛同がないまぜになった反応を引き起こして、「芸術とは何か」という反省を人々に強いた。それ以降、無数の人々、無数の作品によって繰り返し問われる続けることになる問いを、もっとも印象深く初期の段階で示したのだった。

では、数学における泉は、どのようにして生まれ、どのように現代に根付いたのだろうか。

 

4色問題とは、地図を色で塗り分けてエリアを区別する際、少なくとも何色必要か?という問題である。互いに隣り合っているエリア同士は違う色で塗る必要がある。例えば、ドイツとフランスには違う色を使う必要があるが、アメリカとブラジルは隣接していないので同じ色を使っても構わない。

エリアの数が多いほどたくさんの色が必要な気もするが、いやいや、隣と色が違えばいいだけだから、色はそんな必要じゃないぞという気もする。大方の予想では「4色あれば十分」である。しかし、それを証明するのが難しい。

この問題が明解に提示されたのは、1852年だそうだ。ド・モルガンが「生徒からこういう問題を受け取ったのだけど」と手紙に記している。この単純な見かけを持つ問題は、実は一筋縄ではいかず、解決に至るまで結局120年以上の月日がかかった。それも、数学者の頭脳によって解かれとは言いきれいような形で解決がもたらされた。つまり、コンピュータの力を借りて。

 

まず本書冒頭で、4色問題に取り組む上で基礎となる道具、有名なオイラーの定理が紹介される。多面体を考えたとき、

面の数 - 辺の数 + 頂点の数 =2

が常に成り立つというものだ。

f:id:shibafu_beat:20171001233107j:plain

オイラーの定理は、多面体からその着想を得ているがその応用範囲は広い。多面体を光で照らして地面に映すと、平面上に描かれた模様=地図へと射影される。だから、地図について成り立つ性質でもあるのだ。また、この模様を、点を線でつないだネットワーク上のグラフと解釈すれば、グラフの性質を述べているとも言える。(というか、オイラーの定理といえば、今日ではグラフ理論の定理を指すことが普通)

 

オイラーの定理から、すぐにいくつか重要な定理を導き出せる。「いかなる地図も、お隣の数が5つ以下の国を必ず含む」という定理もその一つだ。つまり、次の5つの形の国のどれかは、必ず地図に含まれる(Unavoidable)。これをUnavaoidableな集合という。この定理では4つの要素からなる集合だが、実は膨大な要素からなるUnavoidableな集合が存在する。これが後に4色問題の証明で決定的な役割を果たす。

 

Unavoidableな集合の一例↓

f:id:shibafu_beat:20171001232130j:plain

4色問題への取り組みの途上でもっとも貢献した人を挙げるとすると、ケンプとバーコフの2人だろう。彼らは地図の色数を減らす(Reduce)手法を示した。

例えば、5色で塗られた地図があったとしても、それを上手く塗り替えると実は4色で済むのではないか、という疑問が当然わく。難しいのは、色を減らそうとある箇所を塗り替えると、隣と同じ色になったりして、今度はお隣も別の塗り替えなきゃいけない…といった連鎖が起こって、結局、局所的な塗り替えが地図全体のグローバルな塗り替えを要求してくるという面である。キリが無さそうな話である。しかも、我々は、ある特定の地図だけを話題にしているのではなくて、あらゆる可能の地図が、4色で済むのか?という問いに答えようとしているので、かなり難しそうな感じがする。

そんな中、ケンプとバーコフは、多くのパターンで色数を4まで減らせることを示した(Reduceできるパターン)。

 

Unavoidable, reduceという概念が明解になるとともに、4色問題を解くには何を証明すればよいかも明解になっていった。4色問題は、「UnavoidableReduceできるパターンの集合が存在する」ことを示すことに帰着する。(※理由が気になる人は、一番下に説明あり)

 

Reduceできるパターンかは、ケンプ、バーコフの方法で調べられるとして、Unavaoidableな集合はどうやって見つけるのか?ここで、放電(Discharge)という、一風変わった手法が考え出された。地図の各国が電子をいくつか持っていると想像して、それらを隣国に渡して放電させることによって、電子の分布を変えてゆく。そして、その電子の分布状況から推察して、「必ず地図に現れるパターン」を見つけることができるのだ。

このあたりは、証明をやっているような実験をやっているような不思議な印象を与える。放電させてその後の電子分布を調べる、というは物理実験ではないのか?数学とは他の科学と違って、実験による確認や反証が不要な特権的な分野という数学観が世にあるが、いつのまにか実験もどきが忍び込んできているような感じなのだ。

ともかく、Unavoidableな集合の要素は次々と見つかっていった。しかし、ReducibleUnavaoidableな集合がなかなか見つからない。その探索をもっと速く、膨大なチェックをシステマチックに行わなければならない。コンピュータが活用されるのは必然の流れだった。

1976年、アペルとハーケンが、ついにReducibleUnavoidableな集合を突き止めた。その論文はやたらと長かった。100ページの本文と、700ページの補足、1万個の図、100ページの要約から成り、1000時間のコンピュータの計算時間が費やされていた。決着がついた。地図は4色で塗れる。

 

4色問題に決着がついたは確かだったが、数学者の反応はまちまちだった。否定的な意見は、

  1. 人の頭とペンで解けていないものを証明と呼んでいいのか
  2. コンピュータプログラムにバグがある可能もあって疑わしい
  3. コンピュータにひたすら長い計算をさせただけで、深い洞察や理解を通して解いたわけではない。理解を欠いた解決であり、ひらたく言うと美しくない。

といったものだ。

アペル・ハーケン論文賛成派からの応答は次のようなものだ。

  1. コンピュータは数学者の脳やペンの延長である。
  2. コンピュータにやらせたからこそ、むしろ逆に信頼度が高い(人間よりもミスが少ないはず)

 私からは3番目の論点について述べたい。まず、4色問題とは、ReducibleUnavoidableな集合をひたすら探すということに帰着している以上、この馬鹿らしく長い探索は避けて通れなさそうである。仮に人がコンピュータの力を借りずに長い計算をできたとしても、ひたすら計算しただけという不満は相変わらず残る。

結局、4色問題とは、力技でしか解けない種類の問題である。コンピュータを使ったから不満なのではなく、問題の性質自体が不満を呼んでいるようだ。

 

歴史を振り返ると、元来人間は、ばかばかしく長い計算をひたすら高速にやるということには向いていないので、美しく解ける種類の問題に注力してきた。美しいものにばかり目が向いていたため、美を志向しない数学がありうるということがなかなか意識されることがなかった。しかし近年、コンピュータで力技で解けるようになってきたため、美しくない問題の存在に改めて気づかされた、というのが実際ではないか。

数年前、Googleが、ルービックキューブの面をそろえる最短の手を発表して話題になったが、やはり、従来の意味では美しくない解法であった。

 

美術の世界では、実はデュシャンの「泉」は、展覧会での展示が拒否された。美の規範に合わないのだ。しかし、やがて第2、第3のデュシャンで美術は溢れて、それらが事実化し、美術の一部となっていった。何を美術かと呼ぶかの境界が再定義されていったのだった。数学でも同じことが起きているのだ。

f:id:shibafu_beat:20171001232116j:plain

※「UnvaoidableReduceできる集合」見つかれば、4色問題が解決される理由

背理法4色問題が証明できる。反例として5色以上必要な地図があると仮に想定してみる。そのような反例の中で最小の地図について考える(国の数が一番少ないもの。サイズNとしよう)

UnvaoidableReduceできる集合の存在が証明できたとすると、この最小反例もReduceできる国を含む(Unavaoidableなので必ず含まれる)。その国(Aと呼ぼう)を取り除いて、1つサイズの小さい地図を考えると、それは4色で塗れるはずである(5色必要な反例は少なくともサイズN以上のはずなので)。さて、取り除いた国を復活させて、何色で塗るか考えると、新たな5色目を使うことなく4色でまかなえるはずである(AReduceできるので)。結局、最小反例のはずが、4色で塗り替えられてしまった。矛盾するので、5色以上必要な地図があるという仮定が誤り。どんな地図も4色で塗れる。