四色定理に珍しい新しい証明が登場

四色定理に珍しい新しい証明が登場

コンピュータの助けを借りて1970年代に論争を呼ぶ形で解決された有名な問題を見直すことで、数学者たちはグラフの本質について重要な新しい洞察を得ました。

［画像: Vico Santos for Quanta Magazine］

四色定理は、単純に述べることはできます。隣接する地図において、各地域を4色で塗り分けることは可能でしょうか。隣接する地域が同じ色を共有しないようにします。

序論

数学の問題の中には、解決された後も研究者を長年悩ませ続けるものがあります。証明が現れ、称賛されることさえありますが、不満が残ることもあります。おそらく、議論があまりにも複雑すぎるため、あるいは何かが真実である理由についての深い理論的洞察を与えないためです。理由が何であれ、数学者は、閉じられたと見なされているケースに何度も戻ります。

そのような有名なケースの1つが、数学者が自身の分野について考える方法を変えた問題である四色定理です。

問題は述べるのが簡単で、見るのはさらに簡単です。隣接する地図において、各地域を4色で塗り分けることは可能でしょうか。隣接する地域が同じ色を共有しないようにします。19世紀半ば、この問いは地図製作者にとっては取るに足らない興味のものでした。彼らは4色以上の色を持っており、色使いを制限する特別な理由を見出せませんでした。しかし、アマチュアとプロの両方の数学者にとって、この頭の体操はすぐに執着へと変わりました。

1879年に発表された最初の証明の試みは、コンピュータの助けを借りて11年間続いた後、誤りであることが証明されました。弁護士、医師、そして有名なグラフ理論家からも、さらに多くの誤った答えが出されました。「子供でも理解できる問題です」と、デンマーク工科大学のグラフ理論家であるカルステン・トーマセンは言いました。「それが、これほど大きな挑戦であった理由だと思います。」

この定理は、ほぼ1世紀後に最終的に証明されました。しかし、当時はスキャンダルと見なされたコンピュータ手法が用いられたため、数学者たちは証明そのものの定義を疑問視しました。この問題の地位は、1997年まで議論の的となりました。コンピュータの使用がより一般的になり、より単純なコンピュータ支援による証明が見つかりました。

しかし今日でも、コペンハーゲン大学のコンピュータ科学者であるミッケル・ソロップが言うように、「四色病」は広がり続けています。彼とトーマセンは、自身を罹患者と見なしています。これほど単純な命題であるならば、それが真実であるには、より単純な理由があるはずです。少なくとも、それを実証するための、より効率的な方法があるはずです。

約10年間の作業を経て、ソロップ、トーマセン、そしてデンマーク、カナダ、日本の4人の同僚が、この定理を再び証明するコンピュータ証明を作成しました。

［画像: テーブルを囲んで座っている4人の男性。］

左から：カルステン・トーマセン、カワラバヤシ・ケンイチ、ミッケル・ソロップ、ボヤン・モハルは、最近四色定理を再証明したチームの一員であり、その過程で地図やグラフをより効率的に色付けする方法を明らかにしました。

Courtesy of Mikkel Thorup

この証明は、2026年3月にオンラインで公開され、11月に年次コンピュータ科学基礎会議で発表される予定です。ある意味では、先行する証明よりもさらに複雑です。「彼らは証明を実行するために、惜しみなく電力を使ったようです」と、パリのInriaのコンピュータ科学者であるジョルジュ・ゴティエは言いました。しかし、議論を構築する過程で、研究者たちは地図を色付けするための、はるかに効率的な方法を提供しました。そしてそうすることで、平面グラフと呼ばれる重要な数学的対象の構造的特性について、これまで知られていなかった洞察を発見しました。これにより、他の多くの困難なグラフ理論の問題に進歩する可能性が開かれました。

問題の誤った開始と希望の喪失の歴史を考えると、ゴティエは「今回は本物の結果を見ることができて本当に素晴らしい」と述べました。

コンピュータ化された論争

1852年、数学者のフランシス・ガスリーはイングランドの郡の地図を色塗りしていたときに、4色しか必要ないことに気づきました。彼は、これは常に真実だろうかと思いました。彼は数学者である弟のフレデリックに尋ね、その指導教官であるオーガスタス・ド・モルガンがこの問題に興味を持ち、より広い聴衆に宣伝することにしました。1879年、アルフレッド・ブレイ・ケンプという数学者が解決策を主張したとき、Nature誌にその成果を発表するプレスリリースが出されました。

ケンプは、証明したいことの反対を仮定することから始めました。つまり、4色で塗り分けられない地図が存在するという仮定です。次に、この仮定が最終的に矛盾につながることを示そうとしました。つまり、そのような地図は存在しえないということです。その場合、すべての地図は4色で塗り分け可能でなければなりません。

まず、仮定から得られた4色で塗り分けられない地図は、可能な限り「最小」であると想像してください。もしその地図から任意の国を取り除けば、残りの地図は4色で塗り分け可能になります。次に、地理やその他の無関係な詳細を無視して、地図を平面グラフとして再描画します。各国を点（または頂点）として表し、2つの点が国境を共有している場合は、それらの点間に線（または辺）を描きます。これで、地図の塗り分け問題はグラフの塗り分け問題となり、グラフ理論のツールが利用できるようになります。

［画像］［画像］

Mark Belan/Quanta Magazine

特に、18世紀には、スイスの数学者レオンハルト・オイラーが、平面グラフには多くの有用な特性があることを発見しました。その中には、そのようなグラフのいずれかが少なくとも5つ以下の隣接を持つ頂点を少なくとも1つ含むという保証が含まれます。つまり、あなたのグラフには、ケンプが「避けられない集合」と呼んだ、これらの6つの構成のいずれかが少なくとも1つ含まれているはずです。

［画像］［画像］

そして、あなたのグラフは最小であるため、これらの構成のいずれかを取り除くと、4色で再色付けできるグラフが残ります。ケンプの天才的な動きは、これらの構成のいずれを取り除いたとしても、グラフの色を入れ替える方法を見つけることができると示したことでした。これにより、欠けている頂点を再び追加したときに、5色を必要とせずにすべての頂点を色付けすることが可能になります。

［画像］［画像］

Mark Belan/QuantaMagazine

避けられない構成のそれぞれがこのように「還元可能」であることを示すことによって、最小グラフも結局は4色で塗り分け可能であることを証明しました。つまり、元の仮定は間違っていました。四色定理は真実でなければなりません。

残念ながら、ケンプが証明を発表してから11年後、数学者のパーシー・ジョン・ヒーウッドは、彼の色交換手順に微妙な欠陥を発見しました。取り除く頂点が5つの隣接を持つ場合、ケンプの方法は同じ色が隣接する結果につながる可能性がありました。ヒーウッドは当初、ケンプのアプローチが非常にエレガントであったため、エラーを報告することにためらっていました。実際、ケンプのエラーにもかかわらず、彼の交換手順（今日ではケンプチェーンとして知られています）は、問題の将来の解決策の中心であり続けました。「あなたが名前を付けられるほど興味深い間違いを犯すというのは、興味深いことではありませんか？」とトーマセンは言いました。

結局、ケンプの避けられない集合の最後の構成が還元可能であることを誰も示すことができませんでした。正しい証明は、代わりに8,900の構成からなるはるかに大きく、より複雑なセットを特定し、それらすべてが還元可能であることを示す必要がありました。このタスクは手作業では不可能でした。コンピュータが必要でした。

1976年、数学者のケネス・アッペルとウォルフガング・ハーケンは、可能性のある数をまず1,936の構成に、次に1,482に減らす巧妙な方法を見つけました。その後、イリノイ大学のスーパーコンピュータを使用して、それぞれを適切に還元しました。ついに、四色定理は解決されたと彼らは言いました。

［画像: 数学的な図が含まれた手書きの手紙。］

イギリスの数学者オーガスタス・ド・モルガンは、四色問題へのより広範な関心をかき立てようとしました。「私の学生の一人が今日、私が事実だと知らなかった、そしてまだ知らない事実の理由を教えてほしいと私に尋ねました」と彼は1852年の手紙で、多作な数学者であり物理学者であるウィリアム・ハミルトンに書いています。

Public Domain

彼らは懐疑的な聴衆に迎えられました。当時のコンピュータは恐ろしく、技術的に未知でした。アッペルとハーケンはコアメモリを使用していました。これは、ワイヤーのメッシュに手作業で織り込まれた磁性材料に情報を保存していました。「この証明をどのように信頼できるかについて、あらゆる種類の議論がありました」と、デンバーのコロラド大学の数学者であるエレン・ゲスナーは言いました。「もし電力サージが発生して、証明を無効にする可能性のある1つの構成を見逃したらどうなるのでしょうか？」

それでも、ほとんどの人は「4色で十分」であることを最終的に受け入れるようになりました。イリノイ大学は後に郵便料金印紙にそう発表しました。そして1997年、数学者のチームは、アッペルとハーケンのアプローチを単純化し、コンピュータを使用してわずか633の構成を特定してチェックすることで、この問題を解決しました。今回は、数学界はすぐに結果を受け入れました。

しかし、物語はまだ終わっていませんでした。

誰もいない土地の探索

最新の章は、2015年のデンマークのビーチで始まりました。

日本の国立情報学研究所のグラフ理論家であるカワラバヤシ・ケンイチは、長年の共同研究者であるソロップと共に会議に出席していました。ペアは最近、共同で主要な論文を発表しました（後に、アッペルとハーケンが四色問題で受賞したのと同じ、名誉あるフルカーソン賞を受賞しました）。彼らは今、ニボーグの白い砂浜に立ち、次に何をすべきか考えていました。「私たちは本当に小さなプロジェクトに取り組むことはできません」とカワラバヤシは考えていたことを思い出しました。

四色定理は、彼らのキャリア全体に大きな影響を与えていました。それは彼らに、グラフ理論家になるように促した要因の一つでした。しかし、彼らは1997年の結果の1つの側面、つまり、グラフにn個の頂点がある場合、彩色プロセスにn²ステップが必要になるというレシピは非効率的であるという点に満足していませんでした。

問題は、大きなグラフを渡されてそれを色付けしたい場合、1つの構成を探し、それを削除し、次に別の構成を探し、それを削除し、というプロセスを繰り返す必要があったことです。それは、明らかに4色で塗り分けられるグラフに還元されるまで続きました。

カワラバヤシとソロップは、すぐにトーマセンとサイモンフレーザー大学のボヤン・モハルが加わり、1つずつではなく並列に還元できる構成の避けられない集合を特定したいと考えました。そうするために、同時に還元されている他の構成の彩色に干渉することなく、各構成を還元できることを保証する必要がありました。これにより、4色でグラフを再色付けするための、はるかに高速な方法が得られます。

これらの非干渉構成を見つける方法は？広く探索することです。

1976年と1997年の四色定理の証明では、数学者は接続が少ない頂点のクラスターを特徴とする領域のみに焦点を当てました。カワラバヤシ、モハル、トーマセン、ソロップは代わりに、すべての頂点が他の6つに接続され、辺の三角形配置を形成する、いわゆるグラフの平坦な領域に注意を向けました。これらの領域は、グラフの「誰もいない土地」のようなものを形成します。平坦な領域は通常、構成の還元可能性を証明するために使用される構造を欠いているため、そこで良い構成を特定するのは困難です。しかし、研究者たちは、平坦な領域ははるかに一般的であると考えました。そして、互いに干渉することなく多くの構成を一度に還元および再色付けするには、選択肢をたくさん必要としました。

［画像］

左から、宮下淳之さんと井上悠太さんが、通常は無視されるグラフ領域の重要な構造の探索に貢献しました。

Courtesy of Yuta Inoue

これらの領域での構成の探索には、さらに2人の人材、カワラバヤシの大学院生である井上悠太と宮下淳之さんが加わり、数ヶ月のコンピューティング時間が必要でした。「私たちはかなりナイーブでした」とソロップは言いました。「これほど時間がかかるとは思ってもいませんでした。」しかし、最終的に彼らは新しい避けられない集合にたどり着きました。それは8,202の構成からなる巨大なものでした。しかし、彼らが望んでいたように、それらの構成の多くを同時に還元することが可能になり、かつて多くのステップだったものが数ステップに変わりました。

再び、四色定理は証明されました。そして新しい証明は、はるかに効率的な彩色アルゴリズムを提供しました。n個の頂点を持つグラフの場合、n²よりも大幅に改善されたn(log n)ステップが必要でした。

新しい地平線

1世紀以上前のケンプの失敗した試みと同様に、新しい証明の最大の価値は、見出しとなる結果よりも、グラフの本質に関する新しい洞察にあると言えます。異なる還元可能性の概念を利用し、見過ごされていたグラフの部分を使用することで、この研究はこれらの重要な数学的対象のこれまで知られていなかった構造を明らかにし、数学者にそれらを理解するための新しいツールを提供しました。「一度機械を構築すると、どのような問題が解決できるかがわかります」とゲスナーは言いました。

例えば、グラフ理論家は平面グラフだけでなく、ドーナツ型のトーラスのようなあらゆる種類の表面に存在するグラフにも関心があります。これらのグラフは、新しい研究が平面グラフで明らかにしたものと同じ特性の一部を持っています。これにより、それらについても彩色定理を証明することが可能になります。最新の四色結果の背後にある研究者たちは、現在、これらの技術を使用してこれらの問題に取り組んでいます。障害は残っていますが、トーマセンは「私たちは正しい道を進んでいると思います」と述べました。

一方、四色病は続いています。トーマセンは最近の結果に満足していますが、150年間、アマチュアとプロの両方を悩ませてきた同じ疑問を抱いています。平面グラフであれば常に4色で十分であることの、より単純な説明は存在するのでしょうか？誰もが「なるほど！」と思うような、神話的な1ページ、理論的なひらめきは？

「私が望むのは、コンピュータを使わない証明です」とトーマセンは言いました。「そして、私はそれについて考えるのを決してやめません。」

［画像: スタイリッシュな銀河を描いたイラスト。各銀河は異なる数学的図形または記号を含み、ワームホールのように見えるチューブで接続されている。］

次の記事

数学の謎めいたラングランズプログラムとは一体何なのか？