Hatena::ブログ(Diary)

hiroyukikojimaの日記

2016-06-25

P≠NP問題がざっくり理解できる本

04:15

 

* 追記(6月27日) 最後の紹介した「約数ゲーム」について、メールで解答を教えてくれた人がいたので、最後に追加しました。

 最近、野崎昭弘『「P≠NP」問題』ブルーバックスを読んだので、レビューをエントリーしようと思う。

そもそも、この本を読もうと思ったのは、ある雑誌の企画で「数学の未解決問題」について、ある数学者と討論をすることになっていたのがきっかけだった。ミレニアム問題のいくつかが話題にのぼりそうなので、P≠NP問題についても少し知識を補充しておこうと思ったのだ。

でも、アマゾンのレビューで酷評されているのを読んで、いくぶん躊躇した。それで、少し時間が空いたけど、本屋で立ち読みしてみて、その場で購入した。少なくともぼくには、アマゾンのレビューはミス・ディレクションにすぎないものだとわかった。買って帰って、速攻で読了したが、ぼくの要求にかなった本であった。アマゾンのレビュー欄は、まあ、フリーミアムを利用してサイトに顧客を誘導するための、単なる「釣り」にすぎないコーナーだろう。あそこに労力をかけてdisりを書く精神が理解できない。正直、ご苦労なこったと思う。でも、そろそろ、せめてwikipedia程度の「信憑性チェック」にあたる何かを導入したほうがいいのではないか、と思う。まあ、多くのまともな読者は、アマゾンのレビューは信用しないと思うけど。レビューがひどいので、今回は、楽天のほうにリンクを貼っておく。

アマゾンレビュアーは、本書がなかなか「P≠NP問題」の本論に入らないことにご不満だったようだ。確かに、「コンピュータとは何ものか」から始まって、全体の半分にあたる100ページぐらいまでコンピュータの歴史とか構造の話をしている。レビュアーは、このことに憤慨している。

ぼくも、このあたりは、斜め読みをしてしまった。知っていることが多く、先を急ぎたかったからだ。でもそれは、単に、ぼくが以前にそういうことを読書した経験があるからにすぎず、「不要だから」ではない。P≠NP問題のキモを理解するのは、やはり、コンピュータの仕組み、例えば、2進法とか計算方式とかチューリングマシンとかを知っているべきだし、また、その歴史を知ることも無駄ではないと思う。本書はそういう派生的な知識を含んでいるが、そうでない本は、息苦しく、素人には楽しみのない苦しいだけの登山道となってしまう。

 野崎さんの名著不完全性定理ちくま学芸文庫も、実は、同じ形式をとっていた。数理論理学におけるゲーデル不完全性定理を解説する本でありながら、全体の半分は、ギリシャ数学の話とか公理系の話とか集合論の話をしている。でも、読了したぼくは、この本で最も重要なのはこの部分なのだ、という感想を持った。ぼくの個人的な感覚にすぎないが、ゲーデル不完全性定理を素人が理解するために大事なのは、ゲーデル数でもメタ化でも対角線論法でもない、それは「証明するとはどういうことか」「証明の形式化とは何のことなのか」ということだと思うのだ。それを曖昧なままにしておいては、いつまでたっても、不完全性定理のキモを掴むことはできないのではないか、と思う。このことは、専門家には到底想像がつかないだろう。専門家にとって、「証明するとはどういうことか」「証明の形式化とは何のことなのか」ということは、空気のような存在になってしまっているからだ。

ぼくは、野崎さんの『不完全性定理』以前に、何冊かのゲーデル本、例えば、ホフスタッター『ゲーデルエッシャーバッハ』などを読んだけれど、不完全性定理のキモがわかった気がしていなかった。だから、何冊も手にすることになったのだ。野崎さんの本を読んで、何がわかっていないのかがわかった。それがまさに、「証明するとはどういうことか」「証明の形式化とは何のことなのか」だった。これがつかめてしまうと、後半になってやっと出てくる、不完全性定理の証明の要約が、あまりにピンときてしまったのだ。もちろん、専門家のようにわかっているわけではない。当たり前だ。数理論理で飯を食っているわけではないので、そんな「完全理解」にさく時間も金も必然性もない。欲しいのは「キモの把握」なのだ。それには、野崎さんの表現で十分だった。この手応えは、その後、数冊の不完全性定理の専門書を読破した現在でも、変わることはない。

 数学の啓蒙書のモットーとすべきは次の四点だと考える。

1.ざっくりとした本質を、誤解を恐れず、日常の言語で示す

2.ベンチマークとなる具体例の投入

3.登山道の道しるべを示す

4.動機付け

だから、ごちゃごちゃといろんな知識を披露する、とか、読者が挫折するような証明を子細に書く、とか、面白くもない最新の専門的結果を入れる、とかは逆効果で、モットーに反することなのだ。

本書は、ちゃんとこの4つのモットーを叶えている。

第一に、P≠NP問題のPとNPの違いを、ざっくりと、そして、日常表現で表してる。Pは「多項式時間で判定できる問題」を表すのだけど、NPのほうは理解がやっかいで、それは以下のように説明している。

(#1)非決定論的な選択を許す

(#2)計算量は最も良い場合で数える

(#3)答えがNOの場合は、無視してよい

この3つのインチキを許すアルゴリズムで、多項式時間で解けるもの

何冊かの解説書でNPのことを読んだけれど、この説明がもっとも膝を打つものだった。

2.における本書での「ベンチマーク」は、ハミルトンだ。ハミルトン路とは、点を線で結んだグラフにおいて、すべての点を1回ずつだけ通って出発点に戻るような経路のこと。どんなグラフではそれが可能で、どんなグラフだと不可能なのかを決定するのが、「ハミルトンの問題」である。未解決問題を身近にするには、このような歴史的に有名な問題をベンチマークにするのが得策だと思う。

本書では、このハミルトン路を、NP問題のベンチマークとして、再三説明している。もちろん、どんな計算理論の本にも登場するが、本書ほど丁寧にハミルトン路を説明している本は、少なくともぼくは読んだことがない。本書を読めば、ハミルトン路を見つけるのがなんでやっかいなのかがよくわかる。オイラー路(一筆書き)との違いもよくわかる。ハミルトン路を徹底的にベンチマークとするので、「NP完全」という概念がすんなりと理解できる。

3.の登山道の道しるべも、本書にはちゃんと導入されている。「道しるべ」とは、登山道そのものではない。「もしも登山をするつもりなら、最初にこの道しるべを探し、次にこの道しるべを目指し、とそういうふうに登ればいいのでは?」という示唆を与えてくれることだ。本書を読んだぼくは、「仮に次に何かに進むとするなら」、何を理解すればいいのかがはっきりわかった。NP完全な問題とは、それを決定すれば、NPに属する問題のクラスを完全に決定できてしまう問題のことである。つまり、クラスを代表する問題で、「それだけを分析すればいい」というものだ。例えば、ハミルトン路がそれにあたる。本書によれば、論理式の充足可能性問題(与えられた論理式を真とするような真偽値の割り当てがあるか?)がNPのクラスに属し、しかもP≠NP問題が「充足可能性問題はPに属すか」に帰着されることをクックという人が示したそうだ。つまり、次につまみ食いすべきは、このクックの定理であろうことがわかった。もちろん、つまむかつままないかは、読者の勝手である。このように、本書には、「もう少し精密にP≠NP問題を理解する」ための道しるべが所々におかれているのである。

そして、4.の動機付けについても、本書は十分であると思う。啓蒙書は、読者を「次の啓蒙書に手を出してみよう」とか「専門書を買うだけ買ってみるか」と思わせれば、それだけで成功だ。動機付けとはそういうことである。ぼくは、実際に、本書で動機付けられた。実は、ずいぶん前に、シプサー『計算理論の基礎 1, 2, 3』共立出版を買って本棚に置いてあったが、手つかずのままだった。今回は、野崎さんの本に動機付けられ、この本の3巻を取り出し眺めてみた。そこにはクックの定理の証明が載っており、それを斜め読みして、証明のキモだけは理解することができた。もちろん、精緻に理解したわけではない。当たり前だ。ぼくは専門家ではないので、そんなことをするのは時間と労力の無駄である。趣味と好奇心で、ざっくりと知りたいだけなのである。大事なのは、野崎さんの本を読まなければ、決して、この本を本棚から取り出すことはなく、そして、クックの定理の証明を目にすることもなかった、ということなのだ。

 野崎昭弘『「P≠NP」問題』には、他にも興味深いことがいろいろ書いてあった。例えば、「素数判定」に関して、ルートnまでの素数で割ってみる、というアルゴリズムは指数時間的になってしまうけれど、2002年にインドの3人の数学者によってAKSアルゴリズムというのが発見され、多項式時間で判定できるとわかり、Pのクラスの属する問題だとわかったことがそれだ。ただし、サイズの11次多項式であり、実用的ではないとのことだ。実はぼくは、このAKSアルゴリズム論文を持っていて、以前にテレビドラマ『相棒』の監修をしたとき、利用した経験がある(この監修については、ドラマ「相棒」シーズン12の第2話「殺人の定理」 - hiroyukikojimaの日記を参照のこと)。利用したときには、「そういう判定法があるんだなあ」と思っただけで、それがP≠NP問題と関係するなどと思っていなかった。

中でも非常に興味深かったのは、最後に「余談」として書いてある、次のゲーム。

1. 最初にある自然数N>1を決める。

2.2人で先手・後手を決め、交互に1つずつ「Nの約数」を言う。

3.どちらかがすでに言った数の約数は、もう言うことができない。

4.他に言う数がなくなり、"N"と言ったほうが負け

このゲームは、先手必勝であることが「それほど難しくなく証明できる」という。しかし、一般的で明快な先手必勝アルゴリズムはまだわかってないとのこと。野崎さんは、これを、「存在する」ことと「具体的に求める」ことのギャップの例として、紹介している。ぼくは、大学の講義でゲーム理論を教えている関係上、こういう面白いゲームの例には非常に興味がある。ちょっと考えてみたけど、今のところ、その「それほど難しくない証明」がわかっていない。「具体的なアルゴリズム」を与えずに「存在」を証明するのだから、きっと「超越的な証明」なのだろう。ウェブで検索してみたんだけど、それらしいものが見つからなかった。誰か知ってたら、教えて欲しい。

 というわけで、P≠NP問題について、前記の4点を備え持った啓蒙書をお探しなら、はい、損はさせません。是非、野崎さんの本を読んでごらんなさい。

 

(追記)上記の最後に紹介した「約数ゲーム」について、「証明」が見られる場所をメールで教えてもらいました。これだから、ネットはすばらしい!

「それほど難しくない」どころか、「すごく簡単な」証明でした。

ここに書いてしまうことも可能だけど、自分で考えたい人もおられるでしょうから、書かないで見られる場所にリンクします。

Conjecture and Proof - Miklós Laczkovich - Google ブックス

の 48 ページです。目次のConstructions Proofs of Existenceをクリックすることで閲覧可能です。

ただし、上記の「どちらかがすでに言った数の約数」を「どちらかがすでに言った数の倍数」に代えたバージョンで説明されています。

2016-06-11

久々に音楽のレビューを書く

23:31

 このところ、数学関係のエントリーが続いたので、閑話休題、久々に音楽のレビューを書くことにする。

先週、ジャズのライブに行った。ギタリストマイク・スターンのバンドに、ゲストとしてギタリスト渡辺香津美が加わったライブだった。

いやあ、めっちゃすごいライブであった。とりわけ、ドラマーのデニス・チェンバースがみごとだった。デニス・チェンバースは、すごい昔から知ってたので、すげ〜年寄りのドラマーだと思い込んでたけど、実はそんなでもなかった。ぼくと同じくらいの年齢だった。

マイク・スターンは、ぼくが大学生の頃、マイルス・ディビスのアルバム『ザ・マン・ウィズ・ザ・ホーン』でデビューした天才ギタリスト。ぼくは、このアルバムでマイルスが大好きになったけど、ジャズ通の友人は、「マイルスは、ロックに魂を売った。これはもうジャズじゃない」などと批判していた記憶がある。その批判の中心は、スターンのギターを導入したことにあったんだと思う。ぼく自身は、スターンのギタープレイに痺れまくり、「こんなすごいギターを弾ける若者がいるのか」とぶっとんだものだった。

渡辺香津美のギタープレイを初めて観たのは、74年か75年だと思う。高校のブラスバンド同級生が、「すっげ〜才能の若いギタリストが出たから、一緒に聴きに行こう」というので、ついて行った。あてにならない記憶では、銀座ヤマハのイベント・スペースだったと思う。客は10人くらいしかおらず、みんな床に直に座って、クッションに肘をついてごろごろしながら寛いで聴いた。なんと贅沢な経験をしたことか。デビューほどない渡辺香津美は、若造そのものだったけど、すでにものすごい速いリフを弾きまくっていた。

渡辺香津美に次に注目したのは、中学時代の友人でギター野郎だったやつが、デビュー間もないYMOのライブ音源を持ってきたときで、それに渡辺香津美ギタリストとして加わってた。YMOの曲に、彼のギターが加わると、かっこよさが数倍になった。アルバムが出るのを待ち焦がれたけど、YMOのライブ盤が正式に発売されたときには、ギターの部分がカットされていて残念だった。(すごく後になって、アルバム『フェイカー・ホリック』では再収録された。これは、死ぬほどカッコイイ演奏だぜよ)。

 マイク・スターンのライブは、青山のブルー・ノート東京で行われた。ブルー・ノートは、初めて行ったのだけど、すごく環境のいいライブスペースだった。座って観られるし、お酒を飲んだり、おつまみを食べたりできるし、どの席からでも良く見える。音もすごく良い。やっぱり、大人はこういう環境でライブを楽しみたいものだ。最近、よく行っているライブは、若者が中心のバンドのものなので、「立ちっぱなし・見えない・暴れる」で、ほんと落ち着いて曲を楽しめない。

 これだけじゃ、物足りないので、最近購入したCDのレビューも付け加えるとしよう。買った順で。

まず、最初は、赤い公園のニュー・アルバム『純情ランドセル』

赤い公園は、ここ数年で、最も回数多くライブに通ったバンドである(六本木で赤い公園を観てきた。 - hiroyukikojimaの日記とかスタジオコーストで赤い公園のライブを観てきますた - hiroyukikojimaの日記などを参照のこと)。若い女子4人のバンドだけど、ほんとに斬新にして多彩な曲を作るので、すばらしい。それは、作曲の津野さんが、ものすごくイマジネーションの豊富な人で、さらにはたぶん、とてもよく音楽を勉強しているからできることなんだと思う。今回のアルバムも、非常に多様なジャンルの曲から成っていて、とても楽しい。パンクっぽい曲もあるし、ハードロックもあるし、なんと!ディスコサウンドっぽいのまである。とりわけ、「ショート・ホープ」という曲がサプライズ。これはジャズ・ファンクなフレーバーの曲になってる。ここでの津野さんのギターには、「こういう風に弾けるんだ」とびっくり。歌詞では、「14」のものが、瑞々しい。彼女たちは、まだ、中学生の頃の感覚を失ってないんだね。

貶められたくないし

陰口はたたく

怒られたくないし

良い子にもなれやしない

だってさ。もちろん、シングル・カットされた「Canvas」と「KOIKI」は、赤い公園節でありながら、非常に優れたポップスとなっていて、名曲だと思う。佐藤さんの明るいけど切ない声質がよく映える曲だ。

二枚目は、Tricotのニュー・アルバム『KABUKU EP』だ。

KABUKU EP

KABUKU EP

このTricotも、ここ数年、相当回数ライブに通っているバンドだ(赤坂ブリッツで、Tricotのワンマンライブを観てきた。 - hiroyukikojimaの日記とか渋谷でトリコのライブを観てきますた - hiroyukikojimaの日記とか参照のこと)。女子三人から成るユニットで、変態変拍子の曲調を本領としている。本人たちは、売れ線のJポップをやってるつもりなんだろうけど、ぼくはプログレパンクのジャンルに分類してる(すいません、Tricotの皆さん)。

このアルバムは、5曲から成るハーフ版。面白いのは、1曲はアカペラで、残りの4曲はすべてドラマーが異なっているというところ。4人のドラマーは、オーディションで公募したとか。

今回のアルバムは、とにかく、とにかく、すっげ〜、の一言。リズムがとんでもなく格好良くて、なのに、ボーカルラインがエモくて泣ける。よくこんな曲たちを作れたもんだと思う。

前作のアルバム『AND』は、良いことは良いんだけど、なんというか、変拍子にこだわりすぎで、デビュー当時に持っていたエモーショナルな感じが少しだけ薄くなった感があった。対して、今回のアルバムは、初心に回帰した、いや、もっとパワーアップしたエモーションがあって、すばらしい。

このバンドは、日本語の特性をうまく利用して、非常に自然な歌詞で変拍子を実現している。一聴するだけでは、変拍子だと気づかないくらい自然なボーカルラインになっている。ぼくは、ゼミ生とのバンドで、彼らの曲「爆裂パニエさん」のリード・ギターを弾いた経験があるが、この曲のみごとな歌詞の構成には舌を巻いたものだった。(途中で、ギターだけが一定リズムで弾いて、ドラムとベースのリズムがずれていくクリムゾンチックな場面があるんだけど、結局、ベースとドラムに巻き込まれてしまった。クリムゾンマニアとして情けなか)。

このバンドの本領は、リズムの切れ味とボーカルの切なさのトッピングにある。そういう意味で、今回のアルバムでは、3曲目「あ〜あ」と4曲目「プラスティック」にノックアウトされた。とくに、「あ〜あ」の歌詞は、「仕事がくだらなくなって、嘘の寿退社で会社辞めちゃうOL」の話。この突拍子もない歌詞に、すんごい変拍子が乗ってるのは、のけぞるしかない。4曲目「プラスティック」は、とにかく、YUUMIさんのドラムがかっちょいい。

三枚目は、相対性理論のニュー・アルバム『天声ジングル

天声ジングル

天声ジングル

いやあ、タイトルが、毎度のことながら、あまりにすばらしい。こんな語呂合わせ、どうやって考えるんだろう。

まあ、とにかく、このバンドは、やくしまるえつこの声に尽きる。これは神声だよ、ほんと。この声を保てば、おばあちゃんになっても、青春の歌を歌えると思うぞ。

1曲目「天地創造SOS」の第一声からもう、ノックアウトされちゃう。2曲目「ケルベロス」では、やくしまるさんのアニメ声で「ワンワン」とか言われると、もう、胸の奥の方がくすぐられてたまんないっす。その上、この2曲は、演奏が今までになくハード。とりわけ、ベースラインがすごいと思う。

歌詞も、いつもながら、ぐっと来るものが満載だ。例えば、7曲目「夏至」は秀逸。

13才 夢を見る 14才 闇を知る

15才 恋に溺れては 暑く暑く焦らす夏が来る

 

18才 桜散る 19才 向こう見ず

20才 大人になれずに 暑く暑く茹だる夏が来る

こんな歌詞、書けそうで、絶対書けないと思う。

 さて、来週は、赤い公園とTricotのライブに行く。すばらしい、すんごい演奏、聴かせてね、期待してるぞ。でも、よりによって、なんで同じ週にするかなあ、体力的に不安。相対性理論武道館公演は、大学で期末テストの真っ最中で忙しく、どうするか思案中。

2016-05-23

数学は遠きにありて想うもの

15:08

 実は、また、数学者たちと鼎談をすることになり、そのお題のために、リーマン面・層・コホモロジー群・スキームの勉強を再開した。

 リーマン面というのは、ごく小さい部分だけを局所的に見ると「複素平面」と同一視できるような空間のこと。逆に言うと、複素平面の原点付近の円をたくさん貼り合わせて作り出せる空間のことだ。例えば、リーマン球面は、二枚の円をお椀のように丸めて反対向きにはめ込んで球形にしたリーマン面の一種である。ドーナツ型(トーラス)も円を湿布薬のようにぺたぺたと貼っていけば作れるからリーマン面だ。

 リーマン面コホモロジー群は、小木曽啓示『代数曲線論』朝倉書店で勉強している。この本は以前にも、続・続・堀川先生とキングクリムゾンの頃 - hiroyukikojimaの日記のエントリーで紹介したが、もう一度最初から読み直した。ちなみにこの本は、「代数曲線」と題するより、「リーマン面」と題するべき本だということを書き添えておこう。

講座 数学の考え方〈18〉代数曲線論

講座 数学の考え方〈18〉代数曲線論

 実は、前に読んだときは、「知りたいことと関係が希薄そうで、めんどくさそうな部分」をはしょって読んでいた。具体的には、第3章「リーマン面微分形式」をまるまる飛ばし、そのために第4章の「いろいろなリーマン面」が部分的に読めなくなり、そこも飛ばした。でも今回は、前回飛ばしたところを含め、順を追ってきちんと読んだ。そして、最初からそうすべきだったことに気づき、安易なはしょりをしたことを猛省した。

 多くの数学書は、メインディッシュに対する最短経路で書かれているわけではなく、余計なことがいろいろ書いてある。もちろん著者は、「それが重要である」ないし「知っていたほうが良い」という親心から導入しているのだろう。でも、その「刺身のつま」のせいで、たいていの読者が理解の辛さから脱落することになってしまうことに著者は気を遣うべきだと思う。だから、ぼくはいつからか、そういう「刺身のつま」を箸でよけて読むようになった。

 一方、小木曽啓示『代数曲線論』には、そういう「刺身のつま」がほとんどなかった。導入されているすべてのアイテムは、メインディッシュをより良く吸収するために必要不可欠のアイテムだったのだ。

 たとえば、第3章「リーマン面微分形式」は、「」という数学概念を豊かにイメージするために重要だった。「層」というのは、単純に言えば、リーマン面上の複素関数を思い浮かべればいい。リーマン面は局所的には複素平面の小さい円と同じだから、そこで定義された複素関数のことだ。「層」というのは、「局所で0と一致すれば全体で0、局所的な関数族は貼り合わせて全体の関数にできる」という性質を持つ空間のこと。正則な複素関数は、この性質を備えている。

ただ、それだけをイメージしていると「層」ってそれしかないのかなあ、と貧弱な感覚しか得られない。「層」は、複素線形空間だから、他の例も頭の引き出しに入れておかないと、その不変量であるコホモロジーを理解するときに、高すぎる障壁に突き当たることになる。以前にぼくが突き当たって挫折を余儀なくされたのはその障壁だった。

 本書は、少なくとも「リーマン・ロッホの定理」に到達するまでには(まだ、そこまでしか読んでいない)、無駄なことが一切書いていない。すべてが用意周到に準備されている。それはそれはみごとなものだ。抽象的な概念を具体的に理解するために(たぶん)最もわかりやすい具体例や解説が前もって投入されているのである。

 今回は、ほとんど飛ばしなしに読んだので、「層」「コホモロジー群」「リーマン・ロッホの定理」は理解できた(と思う)。とりわけ、コホモロジー群(チェック・コホモロジー)が、いったい何を表現しようとしているのか、とか、完全系列というのがどう使われるのか、とかを、目が覚めるぐらいに納得することができた。完全系列については、数学科に在籍したときに、「いったい、こりゃ何者なんだ、何の役に立つんだ」と悩ましかったものだった。それが克服できたのは、清々しい。

 本書でのリーマン・ロッホの定理の証明には、完全系列の威力がめっちゃ発揮される。リーマン・ロッホの定理とは、簡単に説明するのは難しいが、層のコホモロジー群に関して、オイラー標数(例えば、[点の数]−[線の数]+[面の数])のような交代和の公式が成立することを主張するものだ。

完全系列というのは、いくつかの線形空間(とか環とか),・・・A, B, C,・・・,と、その間の線形写像(準同型写像),・・・,f, g,・・・の間の関係である 、[・・・→A→(f)→B→(g)→C→・・・]、に関して、(AからBへのfによる像)=(Cの零元{0}のgによるBへの逆像)という等式(要するに、Im(f)=Ker(g))がすべてに対して成り立っているものを言う。線形代数の基本的な定理として、空間Bを(Cの零元{0}のgによるBへの逆像)で割った商空間は、(BからCへのgによる像)と同じ空間になると見なせるから、(Bの次元)=(BからCへのgによる像の次元)+(Cの零元{0}のgによるBへの逆像)である。したがって、さっきの完全系列の定義から、(AからBへのfによる像の次元)=(Cの零元{0}のgによるBへの逆像の次元)が成り立つので、置き換えれば、(Bの次元)=(AからBへのfによる像の次元)+(BからCへのgによる像の次元)という等式(dim B=dimIm(f)+dimIm(g)))が成り立つとわかる。この事実から、[・・・+(Aの次元)−(Bの次元)+(Cの次元)−・・・]という交代和を作ると、打ち消し合いが起きる。だから、系列の最初と最後が空間{ 0 }であれば、交代和は0とわかる。リーマン・ロッホの定理は、この(次元の交代和)=0、を用いてみごとに証明されるのである。

 この定理について、著者の小木曽さんは、次のように書いている。

リーマン・ロッホの定理は次元そのものに関する定理ではなく次元の交代和に関する定理である。オイラー数も交代和だった。日常生活においては和を考えることはあっても交代和を考えることは皆無に近い。それとは対照的に、何故だかよくわからないが、数学では交代和を考えてみると簡明になるということがしばしば起こるようである。

こういう数学者の個人的な数学観のようなものを書いてくれると、本当に楽しくなる。数学者も人間なのだから、定理を見つめた個人的な印象や感慨や感動というのはあるはずで、それを知ることで、読者も数学を人間的で生臭いものとして身近に感じることができるのである。この小木曽さんの言葉を読んだぼくは、「そういえば、行列式の展開定理も交代和だよな」などと記憶が蘇った。ひょっとして、同じアイデアの証明が可能なのだろうか??

 著者の小木曽さんは、昔、ある場所でご一緒したことがあり、何度かお茶を飲んだり、ご飯を食べたりした。そんなある日に、ぼくが、非常に簡単な高校数学レベルの問題を考え出して、それをお見せしたところ、子供のような輝く表情で「それは面白いですねえ、よくできた問題ですねえ」と感嘆してくださった。そのとき、ぼくは、「こんなに優秀な数学者のタマゴが、この程度のことでも、興味津々で楽しい顔をするものなのだ」と感動したことをよく覚えている。そういう小木曽さんの純粋さ、人柄の優れたところ、好奇心溢れるところ、が本書にはよく現れていると思う。

 ただ、やはり、本書を読んでいて、「辛くなかった」と言えば嘘になる。しんどかった。こんなにも工夫して手取り足取り記述してもらってさえ、抽象的な概念を理解するのは「楽しい」より「辛い」のほうが先に立った。こういう抽象物を、何の摩擦もなくイメージ化でき、そうする作業がウハウハと楽しく、真綿のように吸収できる人でないと、数学者にはなれないのだろう、と痛みを持って実感した。そういう意味ではぼくは数学者にはなれない、ということを思い知った。

 その証拠に、「コンパクトリーマン面の正則関数の1次元コホモロジー群の次元が有限である」という基本定理の証明は、読むのをいったんペンディングしている。とんでもなく長い証明で、また、膨大な道具立て(ヒルベルト空間など)が必要だからだ。こういうのを、数学者たちはウハウハと垂涎で読めるのだろうが、ぼくにはため息が出てしまう。こういうところが、数学者に向いているかどうかの踏み絵となるのだろう。

 ぼくは、経済学数学と両方を勉強している。でも、この二つのぼくの中での位置付け・あり方はけっこう異なる。数学は恋い焦がれるほど好きだが、経済学はそうでもない(同業者のみなさん、すいません)。数学には狂おしいほど惹かれるが、経済学はそうでもない(笑い)。それだから、数学にはじれったく短絡的になり、地道な努力が無理で、性急に結果を求めてしまう。一方、経済学のほうでは、冷静で地道な努力ができ、じわじわと距離を狭めることができる。どんな業種であっても、飯を食うプロに自分がなれるかどうかは、「愛のあり方」に依拠するのではないか、と思う。例えば、狂おしいほど音楽が好きな人はむしろプロのミュージシャンには向かないだろう。そうではなく、どんな音楽にもクールに興味を持てて、冷静に分析でき、結果を急がず地道な努力が苦でなく、自分の心と一定程度の距離をおける人がプロ・ミュージシャンになれるのではないだろうか。

さらに言うなら、「プロ」になることが幸せとは限らない。本当に幸せなのは「ファンのほうなのではあるまいか。

 こう考えると、「ぼくが数学者なれなかったのは、必然だったし、むしろ、そのほうが良かったのだ」と今は素直に思える。「数学は遠きにありて思うもの」。心底好きなことは、職業にならないほうがいい。成果もレベルも問われない、そんなに幸せなことはない。それが、今、ぼくの胸中に育つ大きな感慨なのだ。この境地にたどりつくのに、30年もの歳月を費やしてしまったが。。。

 

2016-05-16

メルセンヌ素数とリュカ=レーマー判定法と、そしてペル方程式と

14:10

 「最大の素数が更新された」という報道が今年の1月24日の朝日新聞朝刊でなされたことは、当ブログでも、また、最大の素数が更新された! - hiroyukikojimaの日記でエントリーした。これは2233万ケタという巨大な素数で、アメリカのセントラルミズーリ大学のカーチス・クーパー教授が、世界中のコンピューター約800台のボランティアを利用して発見したものだ。

 発見された素数は、メルセンヌ素数というタイプの素数である。メルセンヌ素数とは、(2のk乗−1)という計算で表される素数。kが素数でないなら、(2のk乗−1)が素数にならないことは簡単にわかるので、kとしては素数だけ試せばよい。今回のものは、(2の74,207,281乗−1)となっており、49番目のメルセンス素数で、当然、74,207,281は素数である。メルセンス素数が発見されることは、偶数完全数(6=1+2+3のように、自分自身を除く約数の和が自分自身と一致する数)が発見されることと同じである。したがって、49個目の偶数完全数が見つかったことになる。ちなみに、奇数完全数はまだ一つもみつかっていないし、「存在しない」と予想されているが、それも証明されていない。

 「任意の」大きな整数素数かどうかを判定する実用的な判定法は、現在のところない。しかし、メルセンヌ数(2のk乗−1)に対しては、実用的な判定法がある。それが、リュカ=レーマー判定法である。これは、19世紀数学者リュカが発見した判定法を、20世紀の数学者レーマーが改良したものだ。

 リュカ=レーマー判定法のやり方は簡単である。まず、リュカ=レーマー数列というのを、次のように作る。すなわち、4からスタートし、得られた数を2乗して2を引いて次の数を作るのである。

4→4×4−2=14→14×14−2=194→194×194−2=37634→・・・

というふうに進んでいく。このn項目をS(n)と書くとき、リュカ=レーマー判定法とは、

素数pについて、(2のp乗−1)がS(p−1)を割り切るとき、また、そのときに限り、(2のp乗−1)は素数である

というものである。例えば、k=5のときのメルセンヌ数(2の5乗−1)は31だが、S(4)=37634は確かに31で割り切れる(おみごと、おみごと)。リュカ=レーマー数列は、正直に計算すると、すぐに巨大な数になるが、判定したい(2のp乗−1)で割った余りで数列を計算(mod計算)していけばいいので、オーバーフローしなくて済むのである。

 雑誌『高校への数学』で素数についての連載をしていることもあって、このたび、このリュカ=レーマー判定法のレーマーによる証明をまじめに読んでみた。読んだのは、和田秀男『数の世界 整数論への道』岩波書店だ。

その証明は、理解できてみると、めちゃめちゃ面白いものだった。

なんということでしょう! 最も重要な役割を果たすのは、いわゆる、「ペル方程式」なのである。

ペル方程式というのは、「(xの2乗)−a(yの2乗)=±1」の整数解を求める問題のことで、数論の研究の中でも歴史の古いものだ。本当は「フェルマー方程式」と呼ばれるべきなのに、誤ってペル方程式と定着してしまったものである。ペル方程式について、詳しくは、拙著『世界は2乗でできている』ブルーバックスを参照してほしい。

証明に使うペル方程式は、a=3のケース、すなわち、「(xの2乗)−3(yの2乗)=1(☆)」である。

この方程式(☆)の整数解は、次のようにして、実にユニークな方法で得られる。すなわち、無理数α=2+√3に対して、(αのn乗)を展開整理し、(αのn乗)=x(n)+y(n)√3と表したとき、x=x(n), y=y(n)が、ペル方程式(☆)の整数解となるのである。しかも、この方法で、すべての整数解が得られる。

面白いのは、この2つの数列x(n)とy(n)が、三角関数(cossin)と類似した、「加法定理」「倍角公式」を持つことなのだ。次のような公式である。

(加法定理)

x(m)=x(n)x(m)±3y(n)y(m)

y(m)=±x(n)y(m)+x(m)y(n)

(倍角公式)

x(2n)=2(x(n)の2乗)−1

y(2n)=2x(n)y(n)

これらの公式を上手に利用すると、いろいろな面白い関係が得られる。まず、

リュカ=レーマー数S(k+1)=2・x(2のk乗)

という関係式がポイントである。

また、3より大きい任意の素数qに対して、

y((q+1)/2)・y((q−1)/2)はqの倍数

が、証明を完成するためのかなめの事実となる。

証明の手法は、典型的な技の組み合わせであり、大学受験の数学問題よりは難しいけれど、数学オリンピック程度のものなので、がんばれば高校生にも理解できる。とりわけ、「2項係数の素因数を評価する」とか、「ある性質を満たす整数が、その性質を満たす最小の整数の倍数となる」という互除法的な発想とか、有名テクニックのオンパレードとなっていて、楽しく、また、随所でうならされる。

こうしてみると、数論の定理というのが、さまざまなアイテムのリンクで成立していて、みごとだなあ、と感心させられる。

 和田秀男『数の世界 整数論への道』は、ものすごい名著だと思うのだけど、現在は版切れのようで残念だ。こんなわかりやすくて、self-containedで、すべての証明を付けている数論の本はほかにないと思う。和田氏が、計算機数学専門家である、ということが、この本のわかりやすさ・面白さと関係あるのではないか、と推測している。最後の章で「すべての素数を表す19変数37次多項式」についての「マチアセビッチの定理」を取り上げ、証明も含めた完全な解説を行っているのが圧巻である。なんと、この定理にも、本質的に「ペル方程式」が活かされているのである。拍手喝采。

2016-04-30

等差数列の中の素数からラングランズ予想へ

15:18

もう、すいぶん前、1年以上前に、黒川信重ガロア表現と表現論日本評論社の一部を紹介した(ガロアの定理の短めの証明が読める本 - hiroyukikojimaの日記)。このときは、ガロアの基本定理」、すなわち、「代数拡大体の中間体と、その自己同型群の部分群が1対1対応する」という定理の、非常に短く、わかりやすい証明がこの本に載っているよ、ということを書いた。それで、この本に載っている他の定理のことも近いうちに書く、と予告してたんだけど、なんと! それから、1年以上も歳月が流れてしまった。

 前々回のエントリー(テレ東ドラマ『電子の標的2』に協力をしました - hiroyukikojimaの日記)で触れたように、今ぼくは、雑誌『高校への数学東京出版に「素数の魅力」という連載を持っていて、そのため、素数について、いろいろと調べ直している。そこで、「ディリクレの算術級数定理」について、どう紹介しようか、と思案して、この黒川先生の本を読み直してみたのである。そんなわけで、このブログにも、小手調べとしてエントリーしてみようと思い立った次第。

 この本の第1章には、「ガロアの基本定理」の最短にして簡明な証明が解説されており、それはガロアの定理の短めの証明が読める本 - hiroyukikojimaの日記のエントリーで紹介した。また、第2章には、「有限アーベル群の基本定理」「ディリクレの算術級数定理」の証明が解説されている。今回は、これについて紹介しようと思う。

 群というのは、1. 結合法則が成り立つ演算を持ち、2. 演算しても変化しない単位元eを持ち、3. 演算すると単位元eになる逆元を持つ、ような代数構造を言う。これらに加えて、4. 交換法則が成り立つ、を要請したものがアーベル群である。「有限アーベル群の基本定理」というのは、有限なアーベル群が、どんな構造をしているかを明らかにする定理。簡単にいれば、nで割った余り算の足し算代数であるZ/(n)たちの和で書け、しかも登場するnたちを小さい順に並べると、約数・倍数関係の列になる、というもの。この定理を拡張して「有限生成アーベル群の基本定理」としたもの(有限生成なので、要素の個数は無限個も可能となる)は、線形代数で重要な定理である「ジョルダン標準形」の証明に使われる。でも、これがまた、わかりずらく、何をやっているかイメージが湧かない証明なのである。それに対して、黒川先生の証明は、(有限部分だけだけど)、非常にわかりやすく、本質がよく伝わり、そのうえ2ページ程度で済んでしまう優れものだ。ジョルダン標準形の証明で挫折した経験のある人は読んでみることをお勧めする。

 「ディリクレの算術級数定理」の証明も、非常にわかりやすく書かれている。この定理は、「初項と公差が互いに素な等差数列の中には、素数が無限個ある」というみごとな定理である。例えば、3n+1型素数も3n+2型素数も無限個あるし、4n+1型素数も4n+3型素数も無限個ある、などなどとなる。これらの中の一部(例えば、3n+2型素数とか4n+3型素数とか)は、ユークリッドが「素数は無限にある」を証明した手法を真似れば、簡単に証明できる。しかし、他はそう簡単ではない。しかも、an+b型(a,bは互いに素)すべてとなるといったいどうやればいいのか想像もつかないだろう。ディリクレは、ゼータ関数の仲間であるL関数を使って、それを証明したわけなのだ。本書には、その証明がたった3ページでまとめられている。 

 ここでは、この定理の証明を、4n+1型素数と4n+3型素数を例にして説明しよう。ポイントは、「どちらの型の素数も、逆数にして加え合わせる無限大になる」を示すことである。有限個しか存在しないなら、こうはならない。そのために、まず、次のようなオイラーを考える

[{1−χ(p)(pのs乗の逆数)}の逆数]をすべての奇素数pにわたって掛け合わせたもの ・・・(1)式

ここでχ(p)は、次の2種類を考える。第一は、すべての奇素数pに対して、χ(p)=1とするもの。第二は、4n+1型素数pに対してχ(p)=1、4n+3型素数pに対してχ(p)=−1とするものである。この二つのχはディリクレ指標と呼ばれるものだ。

この(1)式のlogをとって、積を和に変え、さらに対数関数テイラー展開を適用する。

そして、各pについて、1×(−s)乗の部分と、(2以上)×(−s)乗の部分とに分けると、

log(1)式=(1×(−s)乗の部分)+((2以上)×(−s)乗の部分)

と書ける。第2項が有限値に収束することは高校数学の範囲でわかる。したがって、第1項だけに注目し、

log(1)式=(χ(p)(pのs乗の逆数)の奇素数pをわたる和)+(有限値) ・・・(2)式

という風になる。この(2)式のディリクレ指標χ(p)を第一の場合と第二の場合についてそれぞれ作り、その二通りを合計して2で割ると、4n+1型素数の部分だけが取り出される。これは、4n+3型素数pに対しては、(第一のχに対する(2)式)における係数は+1で、(第二のχに対する(2)式)における係数は−1であることから、打ち消しが起きるからである。

(pのs乗の逆数)の4n+1型素数pをわたる和=(1/2)×[(第一のχに対する(2)式)+(第二のχに対する(2)式)] ・・・(3)式

一方、(第一のχに対する(2)式)は、sを小さくしながら1に近づける(s↓1)と無限大に発散する。これは(1)式が通常のオイラー積から素数2を取り除いたものとなっており、s↓1のとき、全奇数の逆数和に近づくからである。それで、「4n+1型素数の逆数和が無限大となる」ことがわかるのである。これは「4n+1型素数を取り出す」計算だったが、(2)式のディリクレ指標χ(p)を第一の場合と第二の場合についてそれぞれ作り、前者から後者を引き算して2で割ると、4n+3型素数のほうが取り出され、同じ評価法が適用できる。

 ざっくりまとめると、「オイラー積を作るときにディリクレ指標χを掛けておくと、型の異なる素数の係数が異なるようにできる」ということと、「それらのディリクレ指標に適切な集計をほどこすと一つの型だけを取り出すことができる」ということがポイントだ。どんなan+b型素数についてもこれが可能なら、この証明を一般化できる。そして、これは可能なのである。

1からaまでの整数で、aと互いに素なものを集合とすると、それらは掛け算についての群(Z/(n))^{×}を作る。この群から複素数への写像で、乗法を保つ(χ(xy)=χ(x)χ(y))ものをディリクレ指標と呼び、これを用いればよいのである。こうして、「初項と公差が互いに素な等差数列の中には、素数が無限個ある」ということがいっぺんに、そして明快に証明される。

 さて、黒川先生は、この「ディリクレの算術級数定理」を、今話題の「ラングランズ予想」の入り口として用意しているのである。黒川先生の本によれば、「ラングランズ予想」とは、「ガロア群の表現と保型表現が双対の関係にある」というものらしい。先ほどのディリクレ指標χは、乗法群(Z/(n))^{×}の双対なのである。

 この本を読むと、ガロア表現と、保型形式と、それをゼータ関数で結びつける、ということが現代数論の大きなテーマ、夢なんだな、と理解できる。古典的な数学の未解決問題が、個別具体的なのに対し、現代の未解決問題は、普遍的統一的である、というのがよくわかる。そして、前者がパズル的な興味の範疇のものであるのに対し、後者は哲学的な興味の範疇にある、というように感じる。

 直接は関係しないけど、ガロア理論の簡単な入門書なら、ぼくの次の本が役に立つと思う(宣伝、宣伝)。

天才ガロアの発想力 ?対称性と群が明かす方程式の秘密? (tanQブックス)

天才ガロアの発想力 ?対称性と群が明かす方程式の秘密? (tanQブックス)