1852年10月23日、数学の歴史において最も奇妙で、かつ数学者たちを長年苦しめることになるエピソードが幕を開けました。数学者アウグストゥス・ド・モルガンは、同僚のウィリアム・ローワン・ハミルトンに宛てた手紙の中で、教え子から投げかけられた「素朴すぎる疑問」についてこう記しています。
「今日、教え子の一人が、私が事実であると知らなかった（そして今も知らない）事実の根拠を教えてほしいと尋ねてきた」
その学生、フレデリック・ガスリーが提示したのは、兄のフランシスが地図を眺めているときに気づいた、極めてシンプルな問いでした。「どんなに複雑な地図であっても、隣接する領域が同じ色にならないように塗り分けるには、4色あれば十分なのではないか？」というものです。
一見すると、この問題の正しさは疑いようがないように思えます。例えば、アメリカの西バージニア州を考えてみましょう。この州はペンシルベニア、オハイオ、ケンタッキー、バージニア、メリーランドという5つの州に囲まれています。隣接する周囲の州を塗り分けるだけでも3色が必要になり、その中央に位置する西バージニア州を周囲と異なる色にするには、どうしても4色目が必要になります。ド・モルガン自身も「考えれば考えるほど明白に思える」と記しましたが、ハミルトンはこの問題に興味を示しませんでした。しかし、この「明白に見える」問いこそが、数学界を100年以上にわたる泥沼へと引きずり込んでいくことになります。
11年間信じられた「完璧な誤り」
1878年にアーサー・ケイリーがこの問題の証明を公募したことで、ようやく本格的な検証が始まりました。翌1879年、法廷弁護士のアルフレッド・ケンペが発表した証明は非常に説得力があり、10年以上もの間、4色問題は解決されたと世界中から信じられていました。
しかし、数学における「正解」の基準は非情です。1890年、パーシー・ヒーウッドはケンペの証明の中に、特定のケースにおいて手法が破綻するという重大な欠陥を発見しました。ヒーウッドはこの発見について、次のような言葉を遺しています。
「（私の仕事は）建設的というよりは破壊的である」
ケンペの証明は崩れ去りましたが、彼は重要な制約を数学界に突きつけました。それは「すべての領域は一続き（connected）でなければならない」という条件です。例えばアメリカのミシガン州には、五大湖を挟んで飛び地となった「アッパー半島」が存在します。数学的には、こうした飛び地を持つ地域が含まれると、4色では塗り分けられない可能性が出てくるのです。実際の米国地図は4色で塗れますが、この「連結性」の議論は、問題を純粋な「グラフ理論」へと昇華させるきっかけとなりました。
数学の概念を変えた「1,000時間の計算」
ヒーウッドの指摘から数十年、4色問題は「解けそうで解けない」もどかしい難問としての地位を固めていきました。事態が急展開したのは1976年。ヴォルフガング・ハーケンとケネス・アペルが、ついに証明を宣言したのです。
彼らのアプローチは、数学の伝統的な「美学」を打ち砕くものでした。彼らはまず、無限に存在するはずの地図のパターンを、1,936個の「特殊な構成（サブケース）」へと集約しました。もしこれらすべての構成が4色で塗り分け可能であることを示せれば、あらゆる地図で4色定理が成立することになります。つまり、彼らは「無限の問題」を、膨大ではあるが「有限の問題」へと変換するブリッジを架けたのです。
しかし、その1,936個のケースを検証するのは、人間の手には負えない作業でした。そこで彼らは黎明期のコンピューターを導入し、1,000時間を超える計算時間を費やして全パターンを力技で検証しました。
ついに証明が成し遂げられた際、学会の反応は複雑でした。その場にいたドン・アルバースは、聴衆が熱狂的な喝采を送る代わりに、「冷ややかな拍手（polite applause）」で応えたと回想しています。人間が一生かけても検証できない「機械による証明」を、数学者たちはすぐには受け入れられなかったのです。
なぜ数学者はコンピューターを「拒絶」したのか
数学者たちがこの快挙を「忌むべきもの（despised）」と感じた理由は、証明のあり方にありました。伝統的な数学において、証明とは「人間が論理を追跡し、その正しさを完全に理解できるもの」であるべきだったからです。
論理的推論を機械に委ねることへの抵抗感は、実は歴史上繰り返されてきた反応でもあります。17世紀、幾何学的な問題を解くために、当時「新風」だった代数学の手法が持ち込まれた際にも、保守的な数学者たちから激しい反発が起こりました。今回の「コンピューター vs 人間の論理」という構図は、かつての「幾何学 vs 代数学」の対立の現代版だったのです。
「コンピューターによる証明は、本当に証明と呼べるのか？」という哲学的議論は、今日の機械学習や不透明なアルゴリズムが定理を導き出す時代を予見するような、極めて現代的な問いを孕んでいました。
意外な応用：数独は「塗り分け問題」である
4色問題が育んだグラフ理論の視点は、現代の私たちの生活にも意外な形で息づいています。その代表例が「数独」です。
数独の各マス目をネットワークの「頂点（vertex）」、1から9までの数字を「色」として捉え直すと、パズルの正体が浮かび上がります。
- 各マス目（頂点）からは、同じ行・列・3×3ブロック内の他のマス目に向けて、合計20本の「辺（edge）」が伸びていると考えます。
- ルールである「同じ行・列・ブロックに同じ数字を入れない」という制約は、グラフ理論における「辺でつながった頂点同士には異なる色を塗る」というルールそのものです。
数独の81個の頂点と810本の辺が織りなす構造は、地図の塗り分け問題の直系の子孫であり、抽象的な数学がパズルという身近なエンターテインメントに直結していることを示しています。
コメント