制度と政策のデザイン

14/02/10 05:27

土曜日の朝から夕方まで他大学から３名、本学から４名の講師を招いてワークショップ「制度・政策デザインと評価」がありました。延べ６時間くらいそれぞれの方の研究成果を聞かせていただいて、幸せな土曜日でした。

自明なことの自然な連なりが証明

08/02/10 19:08

大学院の学生の頃、河田龍夫先生のフーリエ解析の授業に出ていました。講義は難しくて十分理解できませんでしたが、先生の「証明というのは自明なことを書き並べること」というお言葉が今も記憶に残っています。自明なことの自然な連なりになるまで議論を分解して見せてこそ初めて証明といえるのです。今日、中央大学の松井知己先生の「だれでも証明が書けるー真理子先生の数学ブーとキャンプー」日本評論社が届きました。読むのが楽しみです。

screenshot_01

すべての馬は同じ色

26/09/09 14:46

昨日読み終わった本、新井紀子著「数学は言葉」東京図書、ISBN 978-4-489-02053-7 から引用します。

「すべての馬は同じ色をしている」という命題を次のように数学的帰納法によって証明した。この証明のどこに誤りがあるかを指摘せよ。

馬の数を n をする。n=1 のときは、馬は一頭しかいない。よって、すべての馬は同じ色をしているという命題は正しい。次に馬の数が n のときに命題が正しいと仮定し、(n+1) 頭のときも命題が正しいことを次のように示す。(n+1) 頭の馬を整列させる。前から数えて n 頭目までの馬に着目すると、帰納法の仮定によりすべて同じ色である。一方、後ろから数えて n 頭目までの馬に着目すると、同じく帰納法の仮定によりすべて同じ色をしている。すると、前から２頭目から始まって、後ろから２頭目までの馬はどちらのグループにも属しているから同じ色でなければならない。よって、１頭目から (n+1) 頭目まで全ての馬が同色でなければならない。よって、馬が (n+1) 頭のときも命題は正しい。よって、すべての自然数 n について命題は正しく、すべての馬は同じ色をしていることになる。

deja vu

14/09/09 21:41

先日のシカゴでの学会で非常に難解な発表がありました。途中で耳を傾けているのに嫌気がさして、その次の発表を聞く気力が失せてしまったので、会場を抜け出して椅子に腰掛けていました。そこにオランダの Delft 工科大学にいた K. Roos さんがやって来て「今の話は分かったか」と聞きますので、「全く分からなかった、あまりにも pedantic な発表だった」と答えました。彼も同じ意見だったのですが、いつかこれと同じような会話をどこかで交わしたような気になっていながら、どこで誰と交わした会話かが思い出せません。理由のない既視感かもしれないなと、この経験から３週間近くたった今日、その話を家内にした先ほどまでそう思っていました。でもついに思い出しました。あれはドイツの学会で当時 Trier 大学にいた R. Horst さんと交わした会話でした。そのときも彼が「今の話は分かったか」とか聞いて来たのでした。私の返事はやはり「全然」でした。

円周率

24/08/09 20:41

筑波大学の計算科学研究センターで円周率が2兆5769億8037万桁まで計算され、世界記録を打ち立てたそうです。2002年の時点での世界記録1兆2411億桁の２倍の桁で、計算時間は73時間36分だそうです。昔、計算機科学の授業で文字列照合のアルゴリズムをいくつか教えており、円周率から自分の学籍番号を探し出すという課題を出していました。そのときのノートと円周率のデータが私のサイトに置いてあります。関係ないのですがシカゴの写真です。正面に見えるトウモロコシのような建物の下半分は駐車場です。

CIMG0002

価値はありませんが、まあせっかく書いたので

16/08/09 10:43

チャールストンに来て Amy Langville といろいろ clustering について話をしています。少し前のブログに書いたように、ある不等式が clustering polytope の facet-defining valid inequality であることの証明を書きました。Groetschel-Wakabayashi に２０年も後れているのですが、まあせっかく書いたのですから、捨ててしまうのも惜しいのでここに貼付けておきます。

ClusteringPolytope

今回の講演

13/08/09 21:08

このチャールストン大学での講演スライドです。

Talk@CofCNoBuild

Clustering Polytope

10/08/09 05:00

Clustering Polytope なるものを考え、Nonnegativity Inequality と Connectivity Inequality がその Facet-defining Valid Inequality であることをこの週末に証明しました。証明は Groetschel-Juenger-Reinelt の1985年の論文にある Linear Ordering Polytope に対する議論を参考にして、そんなに大変でなくできました。ですからすでにだれかがやって、どこかに書いてあるかもしれません。図は n=3 の場合の Clustering Polytope です。６次元空間の３次元多面体ですが、それを３次元に描いています。３角錐を２つ張り合わせた図形です。

screenshot_02

チャールストン

02/08/09 19:11

７月３１日の午後にチャールストン (Charleston, SC, USA) に来ました。華氏９０度、湿度９０％という、何とも日本の夏のような気候で、１時間も歩くと疲れたあ〜って感じです。シカゴで乗り換えた際に預けた荷物がこちらの飛行場に届かなくて、着いた日の夜にやっと運ばれてきました。出だしからついていません。写真は College of Charleston (CofC) へ続く Glebe Street と Randolph Hall です。

A Beautiful Fractional Extreme Point

23/06/09 15:12

screenshot_01

あ〜〜〜。

21/05/09 08:52

この数日ずっと考え続けている問題があります。正しいと思い、以前に証明したはずのその証明が不十分ではないかという思いにとらわれたまま夕べも床につきました。どこか変なのです。今朝は4時に目が覚めたので、起きだしました。あたりはまだ暗く東の空に月が輝いていました。ノートを居間のテーブルにおいて、夕べの続きを考え始め、2時間ほどたった頃、以前の証明に不十分な点があったことがわかりました。さらに、どのような条件を追加すればいいのかもわかったのです。何と嬉しいことでしょう。食事を済ませ、鞄を背負って、中学生達と行き交いながらの最寄りのバス停までの6、7分の道は爽やかそのものでした。バスに乗って、すぐに追加すべき条件の意味を考え始めました。言いたい主張はその条件があれば言えます。証明は大丈夫です。しかし、問題が本来定式化している現実に目を移したとき、その条件を仮定してもよいものか、さらにその条件は意味のあるものかが気になります。大学に着くまでずっと考え続けました。あ〜〜〜。

無限かゼロか

17/11/08 11:19

先日読んだ

木村俊一『無限のスーパーレッスン』講談社　ISBN 978-4-06-214108-6

の最後のあたりに「無限か０か」と題した節が有り、次のようなことが書かれていました。考えてごらんなさい。

キャンディー好きのアリスが庭で遊んでいると手品師がやってきて、「キャンディーが欲しければこれをどうぞ」とハンカチを一振りして１番から１０番の番号の付いたキャンディーをくれました。アリスはお礼を言って、１番のキャンディーを食べました。「１０個ではすぐになくなりそうだからあと１０個あげましょう」と、手品師は続いて１１番から２０番までの番号の付いたキャンディーを出してくれました。アリスはまたお礼を言って、２番のキャンディーを食べます。次には、手品師が２１番から３０番のキャンディーを出し、アリスが３番のキャンディーを食べる・・・・・。２人がこれを無限に続けるとキャンディーはいくつ残ることになるのでしょう？

数学の本

18/06/08 09:36

まだ、私が大学院の学生の頃、乗り込んだ東横線の向かいの席に小柄な中年の紳士が、膝に大きな本を広げて座っていました。本と見えたのは実はオーケストラのスコアで、その紳士は91年に他界された指揮者の山田一雄さんでした。周囲の喧騒から切り離されたように山田さんはスコアに目を走らせて、書き込みをしていました。きっと、彼の頭の中ではオーケストラが鳴り響いているんだろうなあ、羨ましいなあ・・・と思ったことが今でも鮮明に記憶に残っています。五線紙に書かれた楽譜が読めないことが悲しいと、ドイツに住む友人の音楽家のmariahofさんにしたことがあります。彼は「でも、山本さんは数学が読めるからいいですよ」と慰めてくれましたが、その言葉があながち慰めばかりではなく、数学が読めることは大いなる楽しみであると感じることがあります。学類で微積を担当し始めて以来、本屋で目に付いた関連の書籍には目を通すようにしていますが、先日来、

E.ハイラー、G.ヴァンナー著、蟹江幸博訳「解析教程（上、下）」シュプリンガー・ジャパン

の頁をわくわくわくわくしながら繰っています。楽しいなあ。

ランダムグラフの最大クラスターの成長過程

19/03/08 15:25

先日来読んでいるスチュアート・カウフマンの「自己組織化と進化の理論」（ちくま学芸文庫）に以下のようなことが書かれています。

１万個のボタンが（中略）ばらまかれているところを想像してみよう。ランダムに２つのボタンを選んで、それらを糸でつなぐ。今度は、このペアを下に置き、さらに２つのボタンをランダムに選ぶ。そして、それを取り上げて糸でつなぐ。これを続けるのである。（中略）しばらくして、ボタンはより大きなかたまり、つまりクラスターへと相互に連結されるようになる。（中略）ランダムグラフの重要な特徴は、糸とボタンの比を調節していったとき、非常に規則的は統計的振るまいを見せることである。とくに、糸とボタンの比が0.5を超えると、相転移が生ずる。この点において、「巨大なクラスター」が突然形成されるのである。

著者の言う比の値 0.5 はちょっと小さ過ぎるのではないかと思いましたので、Javaの練習のつもりでプログラムを書いてN=5000で走らせた結果が下のグラフです。横軸が糸の本数、縦軸が最大のクラスターのサイズです。2785回糸で結んだあたりで最大サイズのクラスターが倍増する様子が見え、小さな飛躍がありますが、その後は結構なだらかな増加であるように見えます。10000本の糸を使ったのですが、最大サイズは5000まで行きませんでした。つまり、全部のボタンがが繋がった状態には届かなかったということです。

これについて、同僚の八森先生からb Bela Bollobas の The evolution of random graphs という論文（Transactions of the American Mathematical Society, Vol. 286, No. 1. (Nov., 1984), pp. 257-274. ）を教えてもらいました。

getConnected

特設講義終了

29/02/08 18:00

今日で、今年の特設講義を終わりました。去年よりもたくさん進むことができました。今年は、内容が易しすぎるのではないかとの印象を持ちました。

計算機科学での出前授業に対するコメントに応えて

15/02/08 15:22

先日、繁野先生の計算機科学の時間をお借りして、私の「問題発見と解決？」の話をしてきました。年度末の卒業研究発表の順位付けの問題を数理計画で解くと言うものです。それに対する学生諸君からのコメントが先ほど届きました。ありがとう。評点に対する教員間の了解が不足しているとの指摘は、全くそのとおりです。つまり、点数で評価をつけるとした場合、5点はいったい何を意味しているのかをあらかじめきちんと取り決めておくべきであるとの指摘です。1つ前の記事にある Balinski-Laraki の論文でも、「共通言語」が不可欠であることが強調されています。そして、"imagine the leaders of the world's powers negotiating an agreement with no common language (and no translators)!" と嘆いています。

BalinskiとLarakiの論文

15/02/08 14:53

Michel Balinski と Rida Laraki が書いた論文 "A theory of measuring, electing and ranking" を読んだ。証明なしに並べられた16の定理は、個々に、そして全体として、私の知識の浅さを恥じ入らせるに十分であった。しかし、なんと快い3時間であったことか。興味がある人は彼らのサイト www.ceco.polytechnique.fr/jugement-majoritaire.html を見てください。

最短経路の本

30/01/08 13:39

先日、大学の本屋で「最短経路の本」というのを見つけた。著者はミュンヘン工科大学の数学の先生のグリッツマンさんとブランデンベルクさんで、翻訳は徳島大学の石田基広先生。舞台はミュンヘン、主人公は高校生のレナと友人（？）のビムとボーイフレンドのヤン。300ページもある本だが、3人の会話で話が進んでいくところは、10年ほど前に久保幹雄さんと書いた「巡回セールスマン問題への招待」と共通点がある。テーマは最短経路問題、オイラー閉路の問題、中国の郵便配達夫の問題、そして最後に巡回セールスマン問題である。ミュンヘンの路線図や名所の写真も織り交ぜてあり、楽しく読んだ。

４色問題

03/02/07 09:25

フリー百科事典『ウィキペディア（Wikipedia）』から４色定理の一部を引用します。

四色定理（ししょくていり／よんしょくていり）とは、いかなる地図も、隣接する領域が異なる色になるように塗るには4色あれば十分だという定理である。但し飛び地のような領域は考えない。実際の行政区分で飛び地があったとしても飛び地とその飛び地の所属する本国は関連せず、別の色であってもよいとする。解決前は四色問題と呼ばれており、未解決の期間が長かったため現在でも四色問題と呼ばれることがある。
（中略）
1879年、アルフレッド・ブレイ・ケンプによる証明が『アメリカ数学ジャーナル』誌上で発表された。この証明は妥当と見なされていたが、1890年になってパーシー・ヘイウッドにより不備が指摘された。しかし、ケンプの証明で使われた論理に沿って、地図を塗り分けるには5色で十分であることが証明された。そして、この問題は、グラフ理論における最も有名な未解決問題となったのであるが、1976年にケネス・アッペル (Kenneth Appel) とウルフガング・ハーケン (Wolfgang Haken) によってコンピュータを駆使して証明された。しかし、あまりに複雑なプログラムのため他人による検証が困難であることや、コンピュータの誤りの可能性を考慮して、この証明に疑問視する声があった。その後、プログラムの改良が進められており、現在、四色問題の解決を否定する専門家はいない。

沢山のquantifierを含んだ命題の否定の補足

16/01/07 05:49

前回の授業の最後に、関数の極限が L であるとの命題の否定が出てきましたが、時間がなく十分に話せませんでしたので、数列の極限の定義とその否定について書いておきます。

数列を a(1), a(2), a(3), ..., a(n), ... で表しましょう。本当は a の右下に小さく 1, 2 とか n とか書きたいのですが、面倒なので、ここではこの表記を使います。この数列が α に収束することは以下のように定義されます。

「任意の正の ε に対して、自然数 N が存在して、
N 以上の任意の n に対して |a(n) - α| < ε となる」

ここで、「任意の」という数学方言は「何でもいいよ、どんなに大きくても、どんなに小さくてもいいよ、あなたの意のままに任せるよ」ということです。

この定義は、大きく見ると

「任意の正の ε に対して、何かがが成り立つ」

という形をしています。ですから、その否定は

「ある正の ε が存在して、その ε に対してはその何かが成り立たない」

です。「その何か」は

「自然数 N が存在して、N 以上の任意の n に対して |a(n) - α| < ε となる」

ですが、これも大きく見ると

「ある性質を持った自然数 N が存在する」

と言っています。ですから「その何かが成り立たない」は

「ある性質を持った自然数 N が存在しない」

です。あるいは同じことですが、

「任意に自然数 N を持ってきても、そのある性質が成り立たない」

です。ですから、ここまでで定義の否定は

「ある正の ε が存在して、その ε に対してはその何かが成り立たない」
＝「ある正の ε が存在して、その ε に対しては、任意に自然数 N を持ってきても、そのある性質が成り立たない」

となります。最後の「そのある性質」とは

「N 以上の任意の n に対して |a(n) - α| < ε となる」

ですから、「そのある性質が成り立たない」は

「N 以上の n で |a(n) - α| < ε とならないものが存在する」

となります。以上をまとめると定義の否定は

「ある正の ε が存在して、その ε に対してはその何かが成り立たない」
＝「ある正の ε が存在して、その ε に対しては、任意に自然数 N を持ってきても、そのある性質が成り立たない」
＝「ある正の ε が存在して、その ε に対しては、任意に自然数 N を持ってきても、 N 以上の n で |a(n) - α| < ε とならないものが存在する」
＝「ある正の ε が存在して、その ε に対しては、任意に自然数 N を持ってきても、N 以上の n で |a(n) - α| ≧ ε となるものが存在する」

となります。

否定される前の命題と比べると、「任意」が「存在」に代わり、「存在」が「任意」に代わっているのに気付くと思います。

証明の完成

01/01/07 05:24

明けましておめでとう。今年もよろしく。じつは正月元旦は私の誕生日です。誰も言ってくれないから、自分で "Happy birthday to ME."

早速、証明の続きです。

p(n) < s < r

なる整数 s で r を割り切るものがあったと仮定します。そのような整数の中で最小のものを t としました。まず

p(n) < t

より、t は最大の素数よりまだ大きな整数ですから、素数ではありません。ですから定義より、t を割りきる２つの整数、たとえば u と v としましょう、が存在して、そのいずれも 1 でも t でもありません。u も v も t より小さい整数になります。しかも、t が r を割り切っていることから、 u も v も r を割り切ります。ここの所大丈夫ですか。ところが、2, 3, 4,..., p(n) の中には r を割り切るものがありませんでしたから、u も v も p(n) より大きいことになります。まとめると、

p(n) < u, v < t かつ　u, v は r を割り切る

となりますが、これは、t の選び方に矛盾します。どうしてかというと、t は上記の性質を持つ整数で最も小さなものだったはずなのに、その同じ性質を持つさらに小さな整数が（２つも）出てきてしまったからです。

結局、これで r は素数であることが示せました。

証終

証明のヒント

26/12/06 13:11

前回は、有限個の素数の最大のもの p(n) に注目して、 p(n) 以下の全ての整数の積に１を加えた

r = (p(n)) x (p(n)-1) x (p(n)-2) x・・・x (2) x (1) + 1

を考えました。これが p(n) 以下の正の整数では割り切れないことを見ました。次に、どんな正の整数でも割り切れないことを示すためには p(n)+1, p(n)+2,..., r-1 のどれでも割り切れないことを示せば十分です。この部分の証明に再び背理法を用います。つまり、

p(n) < s < r

なる整数 s で r を割り切るものがあったと仮定します。そのような整数はあっても r - p(n) - 1 個以下ですから、有限個です。ですから、そのような整数の中には最小のものが存在します。それを t としましょう。さて、この t についてどんなことが言えるでしょうか。続きは年が明けてから。では、よいお正月を。

素数が無限個あることの証明

23/12/06 09:45

昨日、林君が話してくれた「素数が無限個あることの証明」でちょっと問題になったことについて補足します。まずは、その背理法に基づいた証明を思い出しましょう。結論を否定して「素数が有限個である」と仮定します。有限個の素数に小さい順に番号を付けて

p(1)=2, p(2)=3, p(3)=5,..., p(n-1), p(n)

とします。林君の話では

q = p(1) x p(2) x p(3) x・・・x p(n-1) x p(n) + 1

として、q が p(1), p(2), p(3), p(n-1), p(n) のどれよりも大きいこと、さらに p(1), p(2), p(3), p(n-1), p(n) のどれでも割り切れないことを示していました。最後の事実より q は素数であると結論づけていたのですが、この部分に小さな飛躍があると指摘しました。なぜなら、素数とは１と自分自身以外のどんな整数によっても割り切れない整数であって、自分自身以外の素数で割り切れない整数ではないからです。
そこで、q を少し変更して次の r を考えましょう。