Hatena::ブログ(Diary)

hiroyukikojimaの日記

2016-08-20

10を聞いても1しかわからない人のためのゼータ関数入門

02:23

 8月がこんなに忙しい年は初めてで、今まで、全くブログを更新する余裕がなかった。

今回は、更新できない間に、ちょこまか読んだ数学書、小山信也『素数ゼータ関数共立出版紹介をしよう。

ぼくが、中学生のための受験雑誌『高校への数学東京出版素数についての連載をしていることは、何度か書いた。その参考のために、本書を読むことにしたのだ。しかし、単なる参考を超えて、この本はとてもすばらしい本であった。

何がすばらしいか、と言えば、本書はゼータ関数のことを、本当に丁寧に、至れり尽くせりで解説していることである。

数学書の多くは、「1を聞いて10を知る」人に向けてかかれている。極力、最短距離で、最短の労力で、しかもエレガントな方法で定理を導いている。こういう本は、専門家や、将来数学者になる数学少年や、めっちゃ頭のいい人にはこの上なく適切な本だろう。しかし、ぼくを含む、凡庸な、頭の良くない人間には、全くもって挫折感を植え付けられるだけの本なのである。本書は、そういう本と真逆で、ぼくや多くの凡庸な数学ファン、「10を聞いても1しかわからない」人々へ向けて、「痒いところに手の届く記述」で書かれた、超親切な本なのだ。

 とは言っても、本書を完全に理解するにはそれなりの数学知識が必要である。大学1、2年程度の解析学知識、それと、複素解析知識が不可欠だろう。でも、読み方次第では、そういう知識がなくてもなんとかなるかもしれない。この本には何段階かの読み方があると思うからだ。

[深さ1の読み方]:数式は斜め読みするだけで、日本語の部分を中心に読む。

[深さ2の読み方]:数式については、それが何を意味する式かだけ読解し、煩わしいところは飛ばし、主に日本語を読む。

[深さ3の読み方]:数式をちくいち検証しながら、じっくり綿密に解読する。

どの段階を選ぶかは、読者のニーズと知識段階に依拠すると思う。どの段階を選んでも、有意義な読書となることは請け合いである。ちなみにぼく自身は、[深さ2の読み方]をした。以下、各[深さ]をお勧めするレビューを与える。

 [深さ1の読み方の勧め]

本書は、単に定理を与えるだけではなく、それがどんな含意を持っているか、があちこちに書いてある。それらは、ゼータ関数ファンになるのに十分なほど魅力的である。ゼータ関数は、解析学のたくさんの技術がそれこそ「総合商社的」に利用される。本書は、それをただ場当たり的に出してくるのではなく、「その技術を使う必然性は何か」「その技術がどのように効いてくるか」を言葉で説明してくれる。これらの記述を読むと、ゼータ関数というのは数学者の英知の結晶であるなあ、と強く胸が打たれる。

 [深さ2の読み方の勧め]

本書の売りは、ゼータ関数の基本的性質を、省略せずに、しかもできるだけ初等的に証明していることだ。それはもう、至れり尽くせり、痒いところに手がとどくようである。

ゼータ関数ζ(s)とは、ご存じの通り、「(nのs乗の逆数)をすべての自然数nにわたって足し合わせたもの」(Σ(1/n^s))である。ここで、定義域sは複素数全体だが、あとで解説するように、複素数s全部に対してこの無限和で定義されているわけではない、という点が大事だ。

本書ではまず、実部Re(s)が1より大きいsに対して、前記の無限和が広義一様に絶対収束することを丁寧に証明している。基本的だが押さえておきたいことだ。

次に、この領域(実部Re(s)>1)では、ゼータ関数ζ(s)がオイラー積表示「{1−(pのs乗の逆数)}の逆数をすべての素数pにわたって掛け合わせたもの」(Π1/(1−p^(−s)))と一致することを丁寧に証明する。大事なのは、このことだけで、この領域ではζ(s)が0とならないことが同時にわかってしまう、という指摘である。なぜなら、無限積は収束する場合は0とならないからなのだ。このことは、素人には意外な事実であろう。そして、ζ(s)がこの領域では0とならないことは、ゼータ関数の零点を追求するリーマン予想にとっては、とても重要な事実である。

次なる段階として、「(nのs乗の逆数)をすべての自然数nにわたって足し合わせたもの」は、実部Re(s)が1より小さいsに対しては発散することが丁寧に証明される。ゼータ関数ζ(s)はこの領域でも有限値となっているので、多くのアマチュアはここでつまづく。つまり、愚直に無限和を実行すると、発散してしまうわけだから、ゼータ関数ζ(s)はこの領域では「(nのs乗の逆数)をすべての自然数nにわたって足し合わせたもの」ではない、とわかる。こんな大事なことをちゃんと書いている本は少ない。それもそのはず、実部Re(s)<1なる複素数sに対して、くだんの無限和が発散することの証明はそんなに簡単ではないのである。この点について、著者は次のような直感的理由を与えている。

nの増大に伴い絶対値は減少して0に近づき、偏角の絶対値は対数のオーダーで増大していく。したがって、nが自然数全体を動いたときの複素数(1/n^s)の列が、らせん状に原点に向かって収束することは先ほどと同様であり、このような点列の和が収束するかどうかを判定するのは難しい。少なくとも各項が0に収束する上に、らせん状に動くことによってそれらの和には相当な打ち消しあいが起きていると推察されるからである

このような記述は、定理の証明の困難さを示すだけでなく、級数の様子を視覚的に教えてくれる意義を持っている。本書にはこういう記述が満載なのである。実際、この証明は、コーシー列の収束を利用する泥臭いものなのだ。

さらには、細かいことにも、次の提示されるのは、実部Re(s)=1なる複素数sに対してである。sが実部が1で、1とは異なる複素数の場合も発散するのだけど、その証明もそんなに簡単ではない。

そうやって、無限和について丁寧に検討したあと、今度は無限積(Π1/(1−p^(−s)))に対して、丁寧にその収束を検討していく。ここにもさまざまな解析的なテクニックが現れる。

そうした懇切丁寧な検討のあとで、いよいよ、「解析接続」について解説が行われる。すなわち、実部が1より大きい領域で定義された「(nのs乗の逆数)をすべての自然数nにわたって足し合わせたもの」が実部1にもはみだして解析的に拡張でき、実部が1から0の領域にもはみだして拡張でき、という具合に順次拡張できていくのである。このような丁寧な解説を読めば、ゼータ関数というものが、一つの式で素朴に定義されるものではなく、解析的な性質を維持しながら複素平面全体にじわじわとさながら水のように浸透していくものだと直感できるようになる。

 最後に、[深さ3の読み方の勧め]を簡単の書いておく。(まあ、この読み方ができる人がこのブログを読んでると思えないので)。

本書は、おそらく、素数定理「x以下の素数の個数π(x)はx/log xに近づく」をゼータ関数から証明する、最もわかりやすい本ではないか、と思う。しかも、ゼータ関数の零点がどのように素数定理の証明に関わり、そして、それがリーマン予想とどういう関係にあるかも、明快に理解できる。ここまでたどり着けば、自分が素数に関して「進化形ポケモン」になった自覚できるだろう。

深さ3の読み方として、本書は、大学1,2年で教わる解析学の技術のオンパレードであり、その知識のまとめとして利用する、というのがある。ざっと列挙すると、複素数対数、留数、マクローリン展開フーリエ変換オイラーマクローリンの集計法、無限積、ガンマ関数、ウォリスの公式、スターリングの公式、ポワッソン和、アーベルの総和法、などなどだ。これらの基本的な定理や技術が、有機的に結びついて使われるので、スポーツでいうところの「ただただ辛いフットワーク」でない「真剣試合の楽しさ」に匹敵する感覚を得ることができるだろう。

 昔、黒川信重先生と雑談していたとき、黒川先生が「ゼータを中心素材にして、高校数学・大学数学の教科書を再編集したい」ということをおっしゃっていた。そのときは、面白い冗談だな、程度に感じただけだったのだけど、本書を読むにつけ、そういう教科書があったらステキだ、と思うようになった。というか、本書がその先駆けなんじゃないか、とさえ思う。

 ちなみに、ゼータ関数の「入門の入門」には、拙著『世界は2乗でできている』ブルーバックスをどうぞ(笑)。

 

2016-07-28

今日は、新代田でTricotを観てきた。

03:21

 前回(この世で観られる最高の音楽〜Tricot - hiroyukikojimaの日記)に続いて、今回もTricotのライブ・レポートのエントリーをしよう。

今日は、新代田フィーバーで、Tricotの演奏を観てきた。

本当は行く予定ではなかった。実際、期末テストを昨日で終えて、今日は採点に集中しなけりゃならなかった。しかも、さまざまなストレスから胃を痛めていて、今日の今日、かかりつけの医者に行って、胃薬を処方してもらった。そんな日にライブに行くなんて、向こう見ずにもほどがある。

でも、Twitterで、Tricotのメンバーたちが、今日のライブを告知するたびに、行きたい→行かなきゃ→行くのが使命だ、と取り憑かれたようになった。夜になったら、もう、いてもたてもおられず、結局行ってしまったのだ。当日券があるとの予想の下で。まあ、一番大きいのは、新代田というところが、家から電車で数駅の近くにある、ということが大きかったんだけど。

新代田フィーバーは、初めて行ったのだけど、思ったより小さなライブハウスで、混んでいなければなかなかなフィールドだろう。実際、前にTricotを下北沢Queで観たとき(下北沢でトリコ(Tricot)を観てきた。 - hiroyukikojimaの日記)ほどには混んでおらず、しかもダイブもモッシュもなかったので、落ち着いて聴くことができたので良かった。

まず、演奏の感想。

先日に、代官山ユニットで観たとき(この世で観られる最高の音楽〜Tricot - hiroyukikojimaの日記)と、前半の曲は同じだったけど、後半が全く違っていた。とりわけ、新曲をやってくれたのは感動した。新曲のお披露目に立ち会えるなんて、冥利に尽きるぞ。それから、「プラスティック」をやってくれたんだけど、YUUMIさんでないドラマーで聴くのは初めてで、それも新鮮だった。それより何より、大好きなバラード系の曲「食卓」をやってくれたんで、泣きそうになった。ぼくは、アルバム『AND』では、ほんとにこの曲が好きなんだよねえ。この曲の、木田モティホさんのギターのハーモニクスがほんとすばらしいんだよねぇ。ハーモニクスはギターの花。今日は、近かったので、この曲は2カポであることがわかった。ハーモニクスをやりやすいように、2カポなんだろうか。

次に、メンバーについての感想。

イッキュウさんは、いつもとメイクが違うのか、それとも箱の小ささのゆえか、とても美人に見えた(実際、美人なんだろうが)。木田さんは、相変わらずのギターのかっこよさに痺れた。くどいけど、「食卓」のハーモニクスね。せっかくの美人なんだから、もっと、美人を強調する見た目にしたらいいのに、動きは野人でいいから。ヒロミさんは、ほとんど見えなかった。これが、ステージが低い小さい箱の難点なんだよねえ。でも、前回のライブでは、客席に降りてくれて、ぼくらが囲む場所で弾いてくれたからよしとしよう。個人的な感想なんだけど、このごろのTricotの演奏がアグレッシブかつシャープなのは、ヒロミさんのベースによるところが大きいと思う。ドラマーは、代官山のときと同じ、若い男の子だった。山口さんもいいけど、この子も良いね。

 そんでもって、今日の収穫は、新作のTシャツを買ったことと、ずっと欲しかったアーティストブック『爆女』を買えたこと。いや、今、この本のリンクを貼ろうとして、楽天ブックスアマゾン両方で、「爆女」と検索してみたんだけど、エッチなものしか引っかからないぞ、なんでやねん。この本には、DVDがついていることが、買ってみてわかった。それはUstreamで前に配信した、アルバム『AND』からのスタジオライブ。ドラマーが5人も出演する、超贅沢なライブだ。今観てみたけど、すばらしかったあ。木田さんがちゃ〜んと美人メイクしてて、感動。笑。

 今日のライブを観たおかげで、「胃痛なんかに負けるもんか」という活力が沸いた。ライブはいいね。特に、Tricotのライブは。

どうせ、Tricotのメンバーがこのブログを読んでる確率は、1000に3つぐらいだと思うけど、1000が3読んでいる可能性に賭けて、書いてみよう。

彼女たちが、新しいテーマを探してるなら、万が一、探しているなら、イタリアの昔のロックバンドAREA(アレアを聴いてみてよ。例えば、以下。

https://www.youtube.com/watch?v=SAr1tI_-gp8(アレア ライブ)

アレアが20世紀に目指していたことを、この21世紀に実現できるとすれば、それはTricotじゃないかな、と思える。もちろん、いろいろなコンセプトを変形した上での話だけど。リズムの転換と、それと、アグレッシブさね。Tricotならできる。

当時の、いわゆる、ユーロプログレには、PFMとか、オザンナとか、ニュートロルスとか、いろいろいて、どれもすばらしいバンドだけど、「革新的」という意味では、このアレアが唯一無二、孤高の存在だったと思う。とりわけ、ボーカルのディメトリオ・スタトスはすごすぎる(なんで若死にしたかなあ)。聞いた話では、歌詞は「共産党への勧誘」で、このバンドのせいで、多くの若者が党員になったらしいけど、イタリア語のわからないぼくには、真偽のほどは定かではない。

実は、ぼくがまともに観た最初のライブは、高校生のときに観たイタリアプログレバンドのPFM(プレミヤータ・フォーネリア・マルコーニ)なんだよね。このバンドは、キング・クリムゾン詩人ピート・シンフィールドがプロデュースしたため、日本でも流行ったのだ。ずいぶんあとになって、このバンドのイタリア盤を入手したけど、英語盤よりイタリア語盤のほうがずっと良い。

 話が大きく逸れたが、要するに、今日もTricotの演奏がすばらしかった、そういうこと。

2016-07-12

この世で観られる最高の音楽〜Tricot

02:00

先月と今月に、Tricotのライブに行ってきた。

先月は赤坂ブリッツのワンマン、今夜は代官山ユニットで対バンライブ。今夜のライブは、イギリスで活動する日本人バンドBo ningenとの対バンだった。どちらも最高の演奏だった。Tricotのライブは、おおよそ、この世で観れる最高の音楽だと思う

Tricotは、女子3人からなるバンド。ドラムはサポートで、おおよそ、女子ドラマーの山口さんが叩いてるけど、ときどき別の人も叩く。彼女たちの音楽のジャンルは、エモに分類されるのかもしれないけど、とにかくこの変態変拍子の音楽は、ぼくは絶対に「プログレ」に分類する。実際、いくつかの曲は、キング・クリムゾンへのリスペクトが感じられる(思い過ごしだと言われると反論できないけど)。このブログでも何回も紹介しているので、今回はわざわざリンクは貼らないことする。

赤坂ブリッツのワンマンは、それこそ、驚天動地の演奏だった。ここ数年で観たすべてのライブの中で一番の鳥肌ものだったと断言できる。実は、ずいぶん前に1Fスタンディングのチケットを手に入れていたんだけど、ソールドアウトしたため、急遽当日に2Fの椅子席を開放したことを知り、1Fのチケットを捨てて、2F当日券を購入した。大人はお金があるからこういうことができるんだね。

んで、2Fで座って、じっくりと観たライブのすごさと言ったら。とにかく、グルーブ感が半端ない。いつ、こんなにかっこいい演奏が完成したんだろう。ドラム、ベース、ギターのスリリングなシンクロの仕方がめちゃめちゃ素晴らしい。

ブリッツでのライブの見所は、ドラマーが5人も登場したこと。最新のEP盤は、4人のドラマーをゲストに迎えて、1曲ずつ叩いている。そのすべてのドラマーが登場して、各自の曲で叩いたのである。みんな、すごくかっこいいドラミングで、「ああ、今回の楽曲は観てもかっこいいドラムを作曲したんだな」とわかった。とりわけ、YUUMIさん(Flipの女性ドラマー)のドラムを観れたのが嬉しかった。

そして、アンコールでは、ドラマー5人全員での演奏という、もうこういうのはクリムゾンでしかやらないよ、ってな演奏が驚いた。(去年のクリムゾンだって、たかがトリプルドラムだったからね。爆)。こんな贅沢なライブは滅多に観れない。

今日の代官山ユニットのライブは、対バンだったので、前半の約1時間の演奏。ドラマーは、若い男子で、EPの中のどれかを叩いている子だと思う。あの若さであの腕前はすげえ。

今日のライブは、これまでに観たTricotのライブでは最も空いていて、とても見やすかった。こんな近くで観たのも初めてだ。とりわけ、モッシュとかダイブとかなかったので、身の危険を感じずに安心して観られた。演奏は、ブリッツに匹敵するすばらしさで、とりわけ木田モティフォさんのギターのソリッドさには痺れた。こんなギタリスト、女性ではかつていなかったと思う。(ナンバーガールの人がその一人だけど、アグレッシブさが異なる)。

今日のライブには、業界人がいっぱいいた感じがする。とりわけ、最前列で観てた女子の集団は、YUUMIさんとBimbamboom(山口さんの別ユニット)の人ではなかろうか(人違いかもしれないけど)。Bimbamboomのギタリストさんには、赤坂ブリッツで手売りしてたCDを買った際に、サインをしてもらったのだ。

とにかく、最前列のYUUMIさんと思われる人は、ひときわ目立つ美人で、(YUUMIさんでなくても美人ならかまわんとばかり)どうしても近くで見たくなって、じりじりと前のほうに行ったら、彼女が少し後退してきたので、隣で並んで観るはめになり、動揺してしまった、その一曲は頭に残っておらん(もったいな)。

 せっかくだから、Tricotのかっこいい一曲にリンクを貼っておこう(PVは、何をやっちょるんだ君ら、という感じだけど)。

https://www.youtube.com/watch?v=h0Q_y54F070 (Tricot ポークジンジャー)

 ついでに、Tricotネタをもう一つ。

Tricotのボーカリストの中嶋イッキュウさんが、ついこないだ、ソロデビューをした。7月8日の夜中に、Ustreamでなんか放送をするというので、仮眠をとってから、夜中の3時半に起きて観てみたのだけど、その動画は、単にイッキュウさんが新宿から中野へ夜の街を徘徊してるだけのもので、「なんじゃこりゃ」。でも、どことなく心地良いので、1時間もある徘徊映像を最後まで観てもうた。ところが、翌日の真夜中に、イッキュウさんのソロPVが公開されたのだ。それは、まさに夜中に観た徘徊動画にソロ曲をのせたものだった。それが、なんだか、めっちゃ泣ける曲。リンクを貼ろう。これはPVも良いよ。

http://www.ikkyunakajima.com/ (ikkyu nakajima〜sweet sweat sweets)

実は、ぼくは、中嶋さんの「死」とか「別れ」をイメージさせた曲がすごく好きなのだ。とりわけ、デビューアルバムに入ってる「42°C」は、何度聴いても泣いてしまう。

 最後に、Bimbamboomのことの紹介しておこう。

 このバンドは、さっきも書いた通り、Tricotのサポートドラマーの山口さんがリーダーで作った女子だけのファンクバンド赤坂ブリッツの物販で、メンバーが手売りしてたんで、(かわいかったから)思わず買ってもうた。サインもしてもらってほくほくだった。一聴した感想は、「うわ〜、なつかしい。でもかっちょいい」。いまどき、こんな音楽をやろうとする志しは絶賛する。せっかくだからリンクを貼るね。

https://www.youtube.com/watch?v=MjU-i5VdYw8 (Bimbamboom〜HushHush)

これを聴いたとき、大昔、高校生の頃に聴いたハービーハンコックの「カメレオン」を思い出した。っていうか、山口さん、これカバーしてよ(って、読んでるわきゃないか)。

https://www.youtube.com/watch?v=3m3qOD-hhrQ (Head Hunters | Herbie Hancock | 1973)

 とにかくね、Tricotの音楽は、この世で観れる最高の音楽なんだよ。もしも来世がないなら、ゾンビになっても聴きたいのだ

2016-07-09

有名定理にも、短くて、わかりやすい証明が必要なのだ

19:05

 今回は、芳沢光雄さんの名著群論入門』ブルーバックスを紹介しようと思う。

この本は、ずいぶん前に入手したのだけど、読んだ期間が飛び飛びだったので、なかなか紹介のチャンスがこなかった。でも、すばらしい本なので、やっと紹介できて嬉しい。

この本は、タイトルの通り、芳沢先生が「群論」について、非常に初等的な講義をした本である。

群論というのは、19世紀数学者ガロアが「5次以上の方程式には、四則計算とべき根だけで記述できる解の公式がない」ということを証明するときに開発した技法である。基本的には、n個のモノを並べ替える「置換」に、「合成」を演算とする代数計算を導入したものである。ガロアは、n次方程式のn個の解を入れ替える「置換」を代数的に分析することで、前記の定理を証明したわけだ。

群論の発祥は、方程式なんだけど、群という数学的対象があまりに豊かな果実を秘めていたため、20世紀以降は代数方程式に限らず、あらゆる数学の基礎となり、いわば、数学の主役の座を勝ち取った。本書は、そんな群論の初等的な性質を非常にわかりやすく解説した本なのだ。

 この本の特徴を一言で言えば、「群に関する有名定理に対して、とても短く、そしてわかりやすい証明を与えた」ということ。それは、例えば、次の定理たちである。

1. 任意の置換は、いくつかの互換だけの合成で表せる。

2. 置換を一つ決めたとき、その置換を互換の合成で表す方法は複数通りあるが、合成する互換の個数が偶数奇数かは決まっている。

3. 交代群(偶数個の互換からなる置換の成す群)は、置換全体のちょうど半分の要素から成る。

4. n≧5のとき、n次交代群単純群(自分自身と{e}以外に正規部分群を持たない群)である。

これらの定理は、群論では有名定理であり、必ずどの本にも出ている。そればかりではなく、群を利用する数学分野の教科書でも、ほぼ確実に証明が載っている定理たちである。

例えば、1.と2.は、線形代数の教科書にはたいてい載っている。それは、この定理が、行列式を定義するときに必須だからである。行列式は、成分の積に±1を掛けて足し合わせる計算をするのだけど、その際に(+1)を掛けるか、(−1)を掛けるかは、互換の個数の偶奇で決まるのである。また、3.と4.は、さきほど出て来たガロアの定理「5次以上の方程式には、四則計算とべき根だけで記述できる解の公式がない」の本質となる定理である。

でも、多くの教科書や数学書では、これらの定理の証明は、非常にわかりずらく、イメージを掴みづらく、読むのに辟易となってしまう。群論以外の教科書では、それはあまりに深刻だ。本当に知りたいこと(行列式の理論とか、ガロアの定理とか)に早くたどりつきたいのに、これらの群の定理の理解に手間取って、じれったくなってしまうからだ。そうなるのは、多くの教科書や専門書に載ってるこれらの定理の証明が、「古典的でよく知られた証明」であって、決して、エレガントな証明ではないからである。

そのため、ぼくは、拙著『ゼロから学ぶ線形代数講談社を書いたときは、2.の定理の証明を導入することを諦めた。拙著『天才ガロアの発想法』技術評論社では、4.の定理の証明を入れることを諦めた。芳沢さんのこの本での証明を知っていれば、導入のしようがあったかもしれない、と思い、少し努力が足りなかったと後悔している(でも、それらがなくても、良い本なので、未読の人は読んでみてね。笑)。

 多くの数学者は、こういうことに無頓着だ。自分はずいぶん前に既に理解してしまっている定理たちだから、「アタリマエ」の存在になっていて、わざわざ明快に証明しようとする気にならないのであろう。でも、これから学ぶ人のためには、できるだけ理解の労力を引き下げ、できるだけ直観に訴える証明を与えることは大事な貢献であることは言うまでもない。

 芳沢さんの群論入門』には、そういう努力の結晶が盛りだくさんである。それは、芳沢先生が、単なる職業的・数学者の一人である、というだけではなく、これまで数学教育」へもたくさん貢献してきた数学者だからできたことなのだ。

 例えば、1.の証明は、「望むあみだくじを作る方法」を与えることによって証明している。実はぼくは、結果を決めたあみだくじを簡単に作る方法をこの本で初めて知った。作り方も証明もとても簡単である。

次に2.では、まず「恒等置換を互換で表すと、偶数個の合成になる」を証明する。それは、恒等置換であるまま互換の個数を2個ずつ減らす操作から証明する。一般の置換を互換の合成で表す個数の偶奇については、恒等置換のケースに帰着させてしまうのである。

そして4.については、交代群正規部分群Nについて、「Nが長さ3の巡回置換を含めば、交代群になってしまうこと」を証明し、そのあと、「Nが単位元e以外の置換を含めば、必ず長さ3の巡回置換を含む」ことを証明する。場合分けは少し面倒だけど、非常に明快な証明の手順となっている。

 この本は、置換群の初等的な応用もいろいろ書かれていて、ものすごく教育的でものすごく啓蒙的な本となっている。

例えば、偶置換・奇置換の応用として、「15ゲーム」が解説されている。これは、誰もが一度はやったことがあるであろう、正方形のケースに15個の小正方形が配置されており、1から15までの数字が打たれている玩具。一つだけ空いた空白を利用して、小正方形を移動させて並べ替えて、1から15を整列させるゲームである。この「15ゲーム」を紹介した数学書は少し見受けられるけど、「駐車場移動ゲーム」というのは、ぼくは全く知らなかった。これは14台の自動車を、駐車場の空白を利用して移動させて、番号順に整列させるゲームだ。子供や学生にやらせるには適度で楽しいゲームだと思う。どちらも、置換の群論解決することができる。

 さらには、最後の章で解説されている「ラテン方陣問題」は、非常に興味を喚起されるものだった。それは、数学者オイラーが1779年に出した次の問題に由来する。

ここに第1連隊から第6連隊まで6個の連隊がある。各連隊から1級士官、・・・、6級士官それぞれ1人ずつ選出し、合計36人集める。これら36人を配置できる6行6列の正方形の場所に、次の条件(*)を満たすように配置することは不可能ではないか。

(*)出身連隊だけに注目すると、行と列各々の並びには各連隊から1人ずつ出ている。また階級だけに注目しても、行と列各々の並びには1級から6級まで1人ずつ出ている。

これは、「ラテン方陣」についての一つの特殊性質(直交性)を要請するものである。このオイラーの予想が正しいことが証明されたのは、なんと1900年になってやっとであったそうだ。また、n×n方陣についての部分的な解決1960年になって発見されたが、いまだに完全解決には至っていない未解決の問題とのことである。なんか、わくわくするよね。

 数学者の中には、定理の証明は一つ与えれば十分である、と考える人もいるようだ。でも、有名定理に対する、初等的な、あるいは、コストの低い証明の発見は、教育的な意味でも、啓蒙的な意味でも、そして、学問的な意味でさえも、大事なことであると思う。本職の経済学のことになって恐縮だが、経済学で非常に重要な定理に「ワルラス均衡の存在定理」がある。これには、「ブラウワーの不動点定理」が使われる。この不動点定理の代表的な証明法は、本質的にホモロジー群(巻き数)を使うのもの(背理法による)だ。しかし、離散数学の分野で、初等的な証明法が発見されている。それは「スペルナーの補題」というのを利用するもので、ものすごくわかりやすい、コストの低い証明である。そればかりでなく、スカーフという天才的な数理経済学者が、この「スペルナーの補題」を拡張して、ワルラス均衡を具体的に見つけ出すアルゴリズムについての成果を得ている。これは、ホモロジー群(巻き数)を使った「超越的な」証明では不可能なことであろう。

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をクリックすることで閲覧可能です。

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