小学生に出題されるような塗り絵の問題。だが数学界は、これを証明するのに百数十年もの月日を要した。しかも、1976年、ヴォルフガング・ハーケンとケネス・アッペルが導いた解決法は、コンピュータに千時間以上も計算させるというものだった。つまり、証明のプロセスを見た者は誰もいないってことだ。これは本当に数学なのか？G.H.ハーディは言った... 醜い数学は永遠に居場所を見出すことはできない... と。アッペル自身もこう語ったという...
「これはひどい数学だ。数学は、簡潔でエレガントであるべきなのに... と言う人がいた。わたしも同感だ。簡潔でエレガントな証明ができれば、それにこしたことはなかった。」
数学の命題は、単純であればあるほど証明が難しい。まず問われるのは、抽象化された問題を、いかに数学の問題として組み立て直すか？人間社会には、現象は単純明快であっても、問題の本質が理解できていないために、実に的外れな解決策が横行する。数学界の難問として知れ渡れば、アマチュア数学家やパズル愛好家だけでなく、宗教界や文壇からも人々が群がる。ルイス・キャロルやポール・ヴァレリーまでも... 一つの問題に取り組むのに、専門の垣根を取り払った人々が集まる光景を目にすれば、学問のあるべき姿は、むしろこちらの側にあるように映る。
しかしながら、四色問題は「ヒルベルトの23問題」に含まれず、数学界の本流から外された。この問題が解けないのは一流の数学者が取り組んでいないからだ！とも言われ、講義中に証明してやる！と豪語する者もいた。
ただ、ある種のタイル張りアルゴリズムと捉えれば、ケプラー予想とまったく無関係とも言えまい。実際、どちらもコンピュータが解き、大量の演算量と情報パターンを要するという意味では同じ性質を持っていそうである。それは、染色体のような構造体から遺伝情報を見つけるようなものであろうか？本物語でも、染色多項式が鍵を握っているし。無数の細胞から成る人体マップも、人間社会に拡大していく地図パターンも同類項と言えば、そうかもしれない。つまりは、組合せ論の世界！
さらに、地図の二次元パターンを多面体の押し潰した形として眺めれば、面の数、頂点の数、辺の数の三要素に還元できる。つまりは、交点と連結の問題であり、グラフ理論の世界！今日の通信網、交通網、社会ネットワーク、人体ネットワークなどの問題を支える分野である。グラフ理論の最も簡単なケースは、オイラーが提示した「ケーニヒスベルクの問題」に遡る。そう、一筆書きの問題だ。
本書では、アウグスト・フェルディナント・メビウスの「五人の王子の問題」について議論される。それは、王様が死んだら王国を五つに分けなさい、という遺言に発する。前提条件は、どの領土も、他の四つの領土と境界線を共有しなければならない。それが不可能なことは直観的に分かる。つまり、王様の意志は、王国を分けるな！ということだ。
さらに、四色問題をオイラーの「多面体公式」と「数え上げ公式」の応用として物語ってくれる。そして、決め手となった概念は「不可避集合」と「可約配置」であったとさ...
ところで、数学の難題が解決されると、哲学の問題を大きくさせるとは... やはり数学は哲学であったか。
画家は、描こうとする対象を色分けする。描かれる側だって、他とは違うように描いて欲しい。平面上で国や州を区別するには、四色あれば事足りる。地球儀のような球面上でも同じだ。しかし、ドーナツのようなトーラス上で同じことをやろうとすれば、七色が必要になる。空間ってやつは、歪むほど自己主張を強め、差別化を欲するものらしい。これが多様化ってやつか？はたして空間は歪んでいくものなのか。それとも空間の住人の方が歪んでいくのか。狂ったこの世で狂うなら気は確かだ！とはこの道であったか...
はたしてコンピュータを用いた証明法によって、数学の美意識は変わるだろうか？いや変わらないだろう。近現代社会は、コンピューティングに頼らなければ機能せず、ネット依存症やデジタル依存症をますます高める。だからこそ、純粋な美をより欲するに違いない。ただ、その美も人類の手元から遠ざかっていくように映る。現代人は、ますます現実逃避を強めていくというわけか...
この証明で言えることは、少なくともアルゴリズムは正しく、コンピュータの計算さえ間違っていなければ、この証明はほぼ間違いないということ。そして、現代の数学者のほとんどがこの結果を受け入れているということである。
しかしながら、コンピュータは万能ではない。現実に実数演算は近似値で誤魔化され、πですら無理数であるが故に切り捨てられる。もし、浮動小数点演算で答えが合わないと騒ぐ新人君を見かければ、IEEE754 の意義を匂わせてやればいい。危惧されることは、四色定理が証明されたことで、この問題から優秀な数学者が手を引くことだろう。いや、後の天才がエレガントな証明法を発見する希望はある。いずれにせよ、凡庸な酔いどれには同じことか。どんな知識も、著名人や権威者が唱えたというだけで鵜呑みに、いや、ぐい呑みにできるのだから...
1. 問題提起と三枝地図
物語は、オーガスタス・ド・モルガン教授がウィリアム・ローワン・ハミルトン卿に宛てた一通の手紙に始まる。それぞれ、ド・モルガンの法則とハミルトニアンで名を馳せた数学者。ド・モルガン教授は、ある学生から、地図を塗り分ける際、四色で事足りることを指摘されたという。ある学生とは、フランシス・ガスリー。弟フレデリック・ガスリーが言うには、兄フランシスがそれを証明したというのだ。だが、それがどんな証明法かは知られていない。答えを見いだせないド・モルガン教授は、ハミルトン卿にこの問題を持ちかけたところ、反応はそっけなかったという。
さて、四色問題を幾何学的に記述すれば...
まず境界線と交点で構成され、隣り合う二つの領域は一本の境界線を共有する。その場合に色分けするというだけのこと。ただし、一つの交点だけで接する場合は、同じ色で塗ってもいい。この制限がなければ問題が成り立たない。
例えば、一つの領域を四つの領域で囲めば、中心の領域に一色と周りの領域に二色で、合計三色が必要となる。周りの領域が、2以上の偶数個であれば、これで事足りる。だが、一つの領域を三つの領域で囲めば、中心の領域に一色と周りの領域に三色で、合計四色が必要となる。周りの領域が、3以上の奇数個であれば、そうなる。ここには、環との関係を匂い立たせる。ちなみに、二色だけで色分けできる有名な配置に、チェス盤がある。
では、この境界線に着目した時、根本的な素となる配置はあるだろうか？そこで、すべての交点でちょうど三本の境界線が会する場合だけを考える。その素となるモデルに「三枝地図」が紹介される。そして、証明へのアプローチは、四色では塗り分けられないと仮定した三枝地図をリストアップして、それらを反証するという形で展開される。これを本書は「最小反例」と呼び、四色では塗り分けられない地図の中で、これより少ない国からなる地図はどれも四色で塗り分けられるようなものを見つける、という戦略である。
しかしながら、命題を反証するのは一つの例外を示せばいいが、証明となると、すべてのパターンで示さなければならない。帰納法的なアプローチの弱点がここにある。言い換えれば、無限にも見える配置のパターンを有限界に代替できることを示せば、道は開ける...
2. オイラーの多面体公式
まず、四色定理の証明に至る鍵に、オイラーの多面体公式が位置づけられる。面の数を F、頂点の数を V、辺の数を E とすると...
F - E + V = 2
オーギュスタン＝ルイ・コーシーは、この公式が平面上に射影した多面体についても成り立つことを証明した。この時、外部領域を含めるかが問われ、含めないと右辺は 1 となるが、含めると 2 となってまったく同じになる。
これを四色問題に置き換えると...
国の数 - 境界線の数 + 交点の数 = 2 (外部領域を含む)
ちなみに、穴が開いた場合の多面体では次のように拡張される。h は穴の数。
F - E + V = 2 - 2h
そして、h個の穴があいているトーラス上の地図は、下式の H(h) 色で塗り分けられることが、パーシー・ヘイウッドによって予想されたという。
H(h) = [1/2 (7 + √(1 + 48h))]
つまり、穴一つのトーラス(h = 1 の時)では、七色定理が成り立つというわけだ。四色問題(h = 0 の時)では H(h) = 4 となる。ただ、ヘイウッドは、この公式の証明には至っておらず、これまた70年以上もの歳月を要することになる。
3. オイラーの数え上げ公式
次に、地図上の境界線と交点を全て数え上げるという戦略を用いる。
二つの隣国を持つ国がC2個、三つの隣国を持つ国がC3個、四つの隣国を持つ国がC4個... と描かれる時、外部領域を含めた国の総数 F は...
F = C2 + C3 + C4 + C5 + C6 + C7 + ...
それぞれ、二辺国、三辺国、四辺国 ... と呼ぶことにしよう。
どの二辺国にも、境界線が二本あるから、C2個の二辺国は、2C2本の境界線に囲まれる。
どの三辺国にも、境界線が三本あるから、C3個の三辺国は、3C3本の境界線に囲まれる。
どの四辺国にも、境界線が四本あるから、C4個の四辺国は、4C4本の境界線に囲まれる。
よって、境界線の総数 E は、各境界線の両側に国があって二倍になるので、こうなる。
2E = 2C2 + 3C3 + 4C4 + 5C5 + 6C6 + 7C7 + ...
E = C2 + 3/2・C3 + 2C4 + 5/2・C5 + 3C6 + 7/2・C7 + ...
交点も同様に数え上げる。ここで対象とするものは、三枝地図である。
V個の交点のそれぞれに三本の境界線があるので、合計は 3V に思われれるが、各境界線は二個の交点を結んでいるので、境界線が二回ずつ数えられてしまう。よって、3V = 2E としなければならない。
3V = 2C2 + 3C3 + 4C4 + 5C5 + 6C6 + 7C7 + ...
V = 2/3・C2 + C3 + 4/3・C4 + 5/3・C5 + 2C6 + 7/3・C7 + ...
これをオイラーの多面体公式に代入すると、三枝地図の数え上げ公式はこうなる。
4C2 + 3C3 + 2C4 + C5 - C7 - 2C8 - 3C9 - ... = 12
ここで、係数が 4 から順に1づつ減じていることに注目したい。しかも、六辺国が現れない。三枝地図の数え上げ公式では、すべてが 0 になることはありえないし、右辺が正の数である以上、少なくとも地図上には、二辺国、三辺国、四辺国、五辺国のうち一つが存在することを意味する。
しかも、12 という数字が、最小反例になりうるパターンを匂い立たせている。少なくとも正の項の合計が、12個となるような地図だ。本書は、このような形を「隣国は五つだけ定理」と呼んでいる。
「どんな地図にも、五個以下の隣国しか持たない国が、少なくとも一つ含まれている。」
オイラーの「多面体公式」と「数え上げ公式」から得られる帰結は、四色定理の中核をなしているという。四色問題が解けなかった原因の一つは、二次元の思考次元に幽閉されていたからということか...
4. 不可避集合と可約配置
巨匠オイラーの頭脳を借りて、三枝地図を描く場合には、二辺国、三辺国、四辺国、五辺国という基本セルが提示された。このどれかを利用しない限り、三枝地図は描けないということだ。これらを「不可避集合」と呼んでいる。
オイラーの多面体公式と数え上げ公式は、少なくとも正の項が12個となるような地図に、最小反例なるものを匂い立たせていた。12個の領域からなる平面図を多面体に戻してみると、十二面体を思い浮かべる。十二面体と言えば、自然界のデザインに多く見られるパターンだ。例えば、柘榴石の結晶は菱型十二面体構造を持つし、三次元充填を論ずる時に鍵を握る多面体でもある。
一方、「可約配置」とは、最小反例に含まれないような領域の配置のことで、二辺国、三辺国、四辺国はすべて可約配置である。ある地図が可約配置を含んでいる時、これを除いた残りの地図が四色で塗り分けられるならば、必要に応じて塗り直しをすることで、四色の塗り分けを地図全体に拡張することができる。もし、五辺国も可約であることが証明できれば、四色問題は解けたことになるという寸法よ。
そして、四色問題は、いよいよ不可避集合と可約配置を探す段階へ...
5. ヘーシュの放電法、そして、D可約配置とC可約配置
不可避集合を探索するために、ハインリヒ・ヘーシュの考案した「放電法」を利用することが検討される。ちなみに、ヘーシュのアイデアを「放電法」と名付けたのは、四色問題を解決したヴォルフガング・ハーケンだそうな。
三枝地図において、二辺国、三辺国、四辺国は、すでに不可避集合であることが示されたので、まず、五辺国を中心に電荷を +1, 六辺国に 0, 七辺国に -1、八辺国に -2 ... という具合に割り当てる。電荷の総和は、数え上げ公式のやり方と同じ。電荷は周辺にも及び、五辺国では周辺国に 1/5 ずつ放電する。
そして、正の電荷が維持されれば、不可避集合の仲間入り。次は、六辺国を中心に... といった具合に調べていく。つまり、総電荷が変化しないように地図上で電荷を移動させるのが、放電プロセスである。ただ、放電のやり方は周辺領域に対して均等でいいのだろうか？
次に、可約配置はどうやって探索するのか？可約性を見つける根本の考えに、「ケンプ鎖」という概念が紹介される。法定弁護士にしてアマチュア数学家アルフレッド・ブレイ・ケンプの名に因む。それは、中心の領域を囲むリンクを色分けする考え方で、数珠の組合わせをイメージすれがいいだろう。ケンプ鎖の思考原理は、二色だけで塗り分けられた領域に、領域が追加されるごとに二色を入れ替えることによって、ほぼ収まるのではないか... てな具合か。
さらに、ヘーシュはケンプのアイデアを発展させて、二つの塗り分けを「D可約」と「C可約」で区別している。D可約配置とは、環をなす領域の塗り分けが、すべて良い塗り分けに変換できるような配置。「良い塗り分け」という表現が微妙だが、C可約との差別化で気持ちは伝わる。
C可約配置とは、考慮すべき環の塗り分けの個数を減らすような変更を受けてはじめて可約性が証明されるような配置。
そして、四色問題は、放電法とD可約とC可約の議論が中心となっていく。
6. バーコフ・ダイヤモンド
ジョージ・デヴィット・バーコフは染色多項式を考案し、特定パターン「バーコフ・ダイヤモンド」が可約であることを証明したという。彼は最小反例の中に環をなす場合を考えたが、それはケンプのアイデアを一般化する試みだったとか。バーコフの試みから、続々と可約配置が提案されることになる。
ここで、色の数を λ で表記する。λは、3以上の任意の整数。ある国 A は、λの任意の色で塗ることができ、隣国 B は、λ - 1 の任意の色で塗ることができ、さらに、A と B に接する国は、λ - 2 の任意の色で塗ることができる。そして、塗り分ける方法の数 P(λ) において、次式が成り立つ。
P(λ) = λ・(λ - 1)・(λ - 2)2
これが、「バーコフの染色多項式」と呼ばれる。
四色であれば、塗り分けられる方法は、P(4) = 4 x 3 x 22 = 48 通りあるというわけだ。バーコフ・ダイヤモンドを赤(r)、緑(g)、青(b)、黄(y)の四色で塗り絵をする rgby 配列の議論は、染色体構造を想像させる。
ちなみに、四色問題とは直接関係はないが、ジェラルド・バーマンとビル・トゥットが導いた奇妙な帰結を紹介してくれる。
なんと！λが黄金比 τ に対して、λ = τ2 の時、P(λ) が極端に 0 に近づくというのだ。黄金比とは、これ...
τ = 1/2 x √ (1 + √5)
その性質では、次式が成り立つことがすぐに導出できる。
τ2 = τ + 1
染色多項式が黄金比と関係があるならば、バーコフ・ダイヤモンドにも自然の偉大な法則が隠されているのやもしれん..
7. 反証パターンの有限化
1965年頃、ハインリヒ・ヘーシュとカール・デュレがコンピュータを利用して配置の可約性を調べ始める。有限のパターンに絞り込むことさえできれば、後はコンピュータが片付けてくれる。
ところで、ヘーシュの放電法では、反証パターンになりうる悪い配置が、8900種類もあるという。ハーケンとアッペルがやったことは、ヘーシュの放電法を改良して、約2000個にまで絞り込み、シラミ潰しに可約配置であることを示した、ということである。後に、反証パターンは1400個余りにまで整理されたようである。
結局、この手の問題は、反証パターンになりうるケースをいかに効率的にできるか、にかかっているということか。今後も、CPUやメモリなどのリソース性能は向上し、チューリング完全に近づこうとするだろう。だが、不完全性の呪縛からは永遠に逃れられそうにない。人間が出来ることといえば、アルゴリズムを検証することと、実在するコンピュータの計算完全性を問うことぐらいであろうか...
0 コメント:
コメントを投稿