『四色問題』新潮社
ロビン・ウィルソン／著　茂木健一郎／翻訳

歴史上、プロアマ問わず数学者たちを悩ませ続けてきた難問、というのが存在する。「フェルマーの最終定理」が一番有名だろうが、今回扱う「四色問題」も、そんな問題の一つだ。1820年頃、フランシス・ガスリーによって生み出された四色問題は、1952年にフランシスの弟が教授に質問したことをきっかけとして広く知られるようになった。その後、『偉大な数学者のほぼ全員が、四色問題に取り組んだ経験を持っている』（ジョージ・デヴィッド・バーコフ）と言われるほどの挑戦を跳ね除け、ついに1976年に正しいことが証明された…。

がしかし。この四色問題は、数学界にある大きな問いを投げかけることになったのだ。四色問題は、「難問が解き明かされた」という意味でも重要だが、その特異な（少なくとも当時は）証明方法によって、「数学における証明とは何か？」という、非常に本質的な問い掛けを生み出すこととなったのだ。

実際に、四色問題の証明に対しては、こんな反応が出たという。

『わたしに言わせれば、あんな解は数学ではない』
『この定理があんなひどい方法で証明されることを神がお許しになるはずがない！』

散々な評価である。何故こんな苛烈な反応が生まれたのか。

それは、この証明にコンピュータが使われたからだ。四色問題が解かれたことを報じる新聞記事には、こんな風に書かれている。

『本日発表された彼らの証明は、100ページの概要と100ページの詳説、さらに、700ページにおよぶ予備的な研究成果から構成されている。二人はそれぞれ、週に40時間ずつを研究に費やし、コンピュータの使用時間は1000時間に達した。証明には一万点の図が含まれ、コンピュータの出力紙を床に積み上げた高さは四フィート［訳注：約1.2メートル］にもなった』

数学者の多くは、数学に対して「美しさ」と呼ぶべきものを求めているように感じられる。その「美しさ」は、数学をある程度極めなければ見えてこないもので、僕にも当然ちゃんとは分からないが、彼らがそういう感覚を大事にしているということはなんとなく理解しているつもりだ。そしてそういう意味において、ヴォルフガング・ハーケンとケネス・アッペルによるコンピュータを使った証明は、「醜いもの」として快く受け入れられなかったのだ。

また実際的に、「人間がチェック出来ない部分に証明の本質が隠されている」ということに対する不安もある。人間がチェック出来ないものを「正しい証明」として受け入れていいのか、ということだ。また、コンピュータによる証明がなされてしまったことで、四色問題の「美しい証明」が仮に存在するとしても、永遠にそれが得られないことに失望する声もあった。今更「美しい証明」を探し出しても、「四色問題の最初の証明者」にはもうなれないのだから、それに貴重な時間を費やす数学者は出てこないだろうということだ。またコンピュータによる証明では、「何故そうなっているのかという構造の説明がなされていない」という意味で不十分だと指摘する人もいる。

コンピュータによる数学理論の証明については、現在も議論がなされているが、その後も、有限単純群の分類に関する証明などでコンピュータが重要な部分で使われている。今後も似たような事例は出てくることだろう。四色問題は「数学の証明とは何か？」という、非常に本質的な部分に問いを投げかけるという意味でも、非常にエポックメイキングな難問だったのだ。

さて、そんな歴史的背景を説明した上で、ようやく四色問題そのものの話に移ろう。

四色問題は、問題そのものは誰でも簡単に理解することが出来る。フェルマーの最終定理も、問題そのものは比較的理解しやすいが、比べ物にならないほど簡単である。

四色問題：四色あれば、どんな地図でも、隣り合う国々が違う色になるように塗り分けることができるのか？

これが四色問題である。この、一見単純そうな問題が、150年近くも一流の数学者の頭を悩ませたのだ。以下では、この四色問題がどのように証明されたのかという理屈の部分を説明しようと思うが、まずは「数学史上最も有名な間違った証明」の話をしよう。

その証明は、アルフレッド・プレイ・ケンプによって生み出され、1879年に発表された。ケンプは、ロンドンの法廷弁護士にしてアマチュア数学者だった人物であり、彼が考案した「ケンプ鎖」というアイデアを軸にして四色問題の証明に挑んだ。ケンプの証明は広く受け入れられ、実は誤りであったということに、なんと11年間も気づかなかったほどだ。ケンプの証明は確かに間違いだったのだが、いくつかの独創的なアイデアが含まれており、後世の研究に極めて大きな貢献をした。

それでは四色問題の証明の話に移ろう。四色問題の証明の中心にあるのは、「最小反例」という考え方だ。これは、「もし四色問題が間違っているとした場合にどうなるか」という思考から生まれる発想だ。

実は、どんな地図も五色で塗り分けられるという証明は、早い段階で成されていた。だから、「四色問題が間違っている」場合、どんな地図も五色あれば塗れることになる。さてここで、「五色では塗れるが、四色では塗れない地図」を考える（四色問題が間違っている場合、そういう地図が存在するはずだ）。そしてそういう地図の中で、「国の数が最も少ない」を「最小反例」と呼んでいる。

例えば「最小反例」が50の国からなる地図だとしよう。この地図は四色では塗り分けられない。しかしこの地図は「最小反例」、つまり「四色では塗れない地図の中で国の数が最も少ない」のだから、それよりも国の数が少ない地図、つまり49以下の国の地図はそれがどんな地図であれ四色で塗り分けられることになる。これが「最小反例」だ。

さてでは、もし「最小反例が存在しないこと」が証明できたとすればどうなるだろうか？今我々は、「四色問題が間違っていると仮定する」→「そうだとすれば最小反例が存在する」と思考した。もし「最小反例が存在しないこと」を証明することが出来れば、前提となる「四色問題が間違っている」という仮定が間違っていることになる。つまり、「四色問題が正しい」ということが証明される、ということだ（これが「背理法」と呼ばれる証明のやり方である）。

さてでは、どうやったら「最小反例が存在しないこと」を示せるだろうか。ここで登場するのが、「可約配置」と「不可避集合」である。

「可約配置」というのは、「最小反例には含まれないような国々の配置」のことだ。例えば「最小反例」には、二つの辺からなる「二辺国」は存在しない。その詳しい説明はここでは書かないが、「最小反例から国を一つ減らせば四色で塗れること」と「減らした国を元に戻してもなお四色で塗れること」を示すことで、「二辺国」が「最小反例」に含まれない、つまり「可約配置」であることを示すことが出来る。他にも様々な「可約配置」が存在する。

「不可避集合」というのは、「最小反例」に限らず、どんな地図であっても含まなければならない国の配置のされ方のことだ。例えば「三枝地図」と呼ばれる地図には、「二辺国、三辺国、四辺国、五辺国の内少なくともどれか一つが含まれていなければならない」とわかっている。こういう、地図を作る上で避けがたい国の配置の条件のようなものを「不可避集合」と呼んでいる。

この二つから、「可約配置の不可避集合」を見つけることが出来れば「最小反例が存在できないこと」を示せる。

「不可避集合」というのは、地図を作る上で避けられない国の配置のことであり、どんな地図（もちろん「最小反例」も例外ではない）にも含まれていなければならない。一方「可約配置」というのは「最小反例」には含まれない国の配置である。ということは、「可約配置の不可避集合」は、「どんな地図にも（最小反例にも）含まれていなければならない国の配置だが、最小反例には含まれない配置」である。「最小反例に含まれていなければいけないのに、最小反例には含まれない配置」など存在するはずがないので、つまり「最小反例は存在しない」ということになるのだ。

ここまでの議論によって、「可約配置の不可避集合」を見つければ、四色問題は証明されたことになる。そしてコンピュータによって「可約配置の不可避集合」を発見し、実際に四色問題が証明された、ということなのだ。

僕個人としても、コンピュータによる証明というのはモヤモヤする部分があるが、しかし人工知能がますます進化していくだろう現状において、どんな分野においても「理屈は分からないが、人工知能が判断したことを受け入れざるを得ない時代」がやってくるのもまた不可避に思われる。そういう時代を生きる僕らには、また違った意味で考えさせる証明であるようにも感じられる。

『四色問題』新潮社
ロビン・ウィルソン／著　茂木健一郎／翻訳