Mathematics @ Floating Log

# LattE

LattE というソフトウェアをインストールしなければいけなかったのだが、かなりクラクラする代物。 ソフトウェアのできの話ではなく、インストール方法。 最初は ebuild を作ろうかと思ったけど、無理(やってやれないことはないだろうけど手間ばかり掛る)。

linux だと ./install だと一発です、と書いてあるものの、こちとら OS X なので案の定うまくいかない。 インストールのステップを追ってやってみようと中身を見たら、まずはシェルスクリプト代わりのC++プログラムをコンパイルさせる。 実質的に system しか呼んでないプログラムって。

malloc.h が OS X には無いのでコメントアウトする。 本当は適当なマクロで #ifdef して分岐すべきなんだろうけど、まあ自分用だからいいか。

cdd というプログラムはバイナリーで収められているのだが、ELF なので OS X では実行できない。 cdd+ の 0.77dev1 というのが一緒にあるので、まあこれだろうと思ってコンパイルしたら通らない。 仕方ないのでぐぐったら、どうもスイスにいる日本人らしき人が作者。 cdd and cddplus Homepage に 0.77a というのが置いてあって gcc 4.1 でコンパイルできる、と書いてあるのでそれをもらってきてコンパイル。

ということでどうやら動く。 C++ をシェルスクリプト代わりに使う、というのが、何はともあれ本日一番の衝撃。

# UFD

一意分解整域についてまとめてみていた(因数分解について一般論を考える一環として)。 素元分解から話を進めても、既約元による一意分解から話を進めてもいい、というのを再現しているうちに別のまとめ方もあるような気がしてきた。 分解できるということの本質は有限積に収まることにあって、それは自然に既約元の積で止まる。 一意性を保証するのが素元の役割なので、そのことを加味すると結局

• 任意の元は有限積にしかならない
• 既約元ならば素元

という二つの条件を採ってもいいことになるようだ。 特に後者は性質として示すことが多く、定義にしてもいいという意見は見たことがない気がする。

追記(2008-11-21): 有限積という条件はイデアルに話を移せばネーターということで、その場合「既約元ならば素元」と UFD の同値性は知られた結果だった。

# 多項式: X とは何か

今日はいわゆる「変数」あるいは「不定元」と言われる X に意味付けを与えてみる。 つまり、天下り的に X を与えてしまわないで、自然に(と思ってもらえるかどうかは判らないが)導出されるものであることを納得してもらう。

前回とは打って変わって、多項式は多項式関数のクラスとして考える。 可換環 R を係数とする多項式 f は R-環 S ごとに定義される関数
f_S: x |-> a0*1_S + a1*x + ... + an*xⁿ
を寄せ集めたもの(集合と呼んでいいのか判らないからとりあえずクラスとしておく)である(1_S は S の単位元)。 a0*1_S + a1*x + ... + an*xⁿ という表現は、1_S と x から有限回の加算、乗算、R の元によるスカラー倍(ここでは * で表わしている)で得られる S の元を全て表わせることに注意しておく。

これらクラスに対し、和・積・スカラー倍を改めてそれぞれの R-環 S における和・積・スカラー倍に対応するように定義する。 つまり、
(f + g)_S(x) = f_S(x) + g_S(x)
が全ての S の全ての x について成り立つように和を決める等。

ここで特別な元をピックアップしよう。 X⁰ を全ての S について
X⁰_S(x) = 1 * 1_S
であるものとする。 すると、1 * 1_S はいつでも 1_S だから全ての S について積の単位元になり、今考えている多項式の集合の中で X⁰ は積の単位元になる。

次に 1 以上の自然数 i に対し Xⁱ を
Xⁱ_S(x) = 1 * xⁱ
であるものとする。 注意としては、今のところ Xⁱ というのがただの一纏まりの記号であって X の i 乗は意味していないということ。

と注意を述べておきながら、これら(i=0 も含めた) Xⁱ 同士の積を考える。 と X の i 乗と同じ規則を満たす(X⁰ を単位元とし X¹ で乗法的に生成される可換モノイド)、ということになり、ある意味で X が何か解った。 すなわち、Xⁱ という多項式関数のクラス達があって、それらを集めると普通の「変数」X の役目を果たせる、ということだ。

ということで着地点を X に絞ってみたが、今日の中心テーマは「多項式は多項式関数」と考えてみたかったということだ。 普通は「多項式は多項式関数ではない」というような扱いがあって「代入」という操作を改めて定義するわけだが、最初から関数ならそんな面倒なこともない。 それに代入をした値の和や積が和や積に代入した値と等しい、という性質を導くのも、話が逆になってすっきりしたと思う。 ただし、「関数」そのものではなく数学的には関数のクラスということになってしまったのでそこは少し解りづらい。 プログラム的にはジェネリックというかダックタイピングというかそういう処理になると思うのだが、そこはまだ詰めて考えていない。

# 多項式: 今日の定義

多項式の定義と言えば X から始めるかブルバキ風に自然数から可換環への写像だと言い切るかなのだが、そういうのに飽きてきたので形式文法風に考えてみる。

＜多項式＞ ::= ＜単項式＞ | ＜単項式＞ + ＜多項式＞
＜単項式＞ ::= ＜数＞ X ^{＜自然数＞}

＜自然数＞は 0 を含んでいる意味で使っている。 ＜数＞をどう指定するかに依って、ここで定義しようとしている多項式の属する集合が変わってくる。 つまり、＜数＞を可換環 R の元と定めれば R 上の多項式を定義することになる。 この辺りはあまり形式文法風ではない。

ともかく、この文法の有限回の適用で得られるものを「多項式」と呼ぶことにする。

ここで「多項式」と鈎括弧を付けた訳は、この「多項式」は大量に同じ多項式と見なされるべきものを含んでいるからである。 たとえば、1X¹ + 3X² に対し、1X¹ + 2X² + 1X² という同類項をまとめていないもの、1X¹ + 3X² + 0X⁴ という無意味な項が付いているもの、また 3X² + 1X¹ という項の順序が入れ替わったものなどがある。 細かい話なのではあるが、そういうものは「等しい」という同値関係で割ってやると、同値類の代表として例えば昇順に並んだ 0 でない項の和という形が取れる(零元は仕方ないので 0 で表わしておく)ことになる。 これで多項式ができた。

利点は…何だろう？ 「多項式は単項式の和です」と定義で言い切っているところかな。 同値類とか持ち出してしまったところで全然解り易くないものになってしまうけど。

# 幅のない長さ

線とは幅のない長さである、というのがユークリッドの定義だったと思う。 が、紙に「線」を引こうとすると幅ができてしまう。 だから、それは線ではない。

では、線を図示できないのか、といえば、できる。 できることに思い至った。 線を引かなくても線が見える。 二つの領域の境界に輪郭線が。

そもそも数学の定義はどこかで無定義術語に行き当たり、それが妥当だと思われるためには人の直感に頼るしかない。 妥当性の根拠は結局生物学的なヒトという共通性である。 ということで、人は「幅のない長さ」をユークリッド以前から知っている。 見たことがある。 それが多分、物の輪郭線なのだ。

輪郭線は、西洋画の伝統では排除される。 見た通りに描く、と言われる意味は、できる限り脳内で処理される前の光の様子を再現する、ということで、輪郭線の抽出は脳内の作業だから描いてはいけないのだろう。 つまり、そこには幅を持って再現される何物も無い。 が、認識の焦点をそこに当てることができるという意味では何かが有る。 それが輪郭線であり、幅の無い長さである。

(この辺りの話は昔読んだ養老孟司の本に影響されているような気がするが、確認するのが面倒なのでしていない。)

ところで、ジョルダンの閉曲線定理という定理がある。

c を平面 R² 上の単純閉曲線（ジョルダン曲線）とする。 このとき、c の像の補集合は二つの互いに素な連結成分から成り、一方の成分は内部と呼ばれる有界領域であり、他方の成分は外部と呼ばれる非有界領域となる。 また、c は両成分の境界を成す。

ジョルダン曲線定理 (フリー百科事典『ウィキペディア（Wikipedia）』)

証明しようとすると大変なことで有名だが、上で見たように線を物の(この場合平面図形の)輪郭線だと思うと自明以外の何者でもなく思える。 何を出発点に何を証明しようとしているのか、というところが問題なんだな。

# call/cc で古典論理

POPL '90 の論文で、Timothy G. Griffin A Formulae-as-Types Notion of Control というのがそれだ(リンク先は citeseer)。

# アキレスと亀

俊足で知られたアキレスがのろまな亀と競争するとき、ハンデをもらって先に出発した亀にアキレスは追い付けない。 という例のパラドックスである。

その証明は、次のようなものであった。

1. アキレスが亀の出発した地点に到達したとき、亀はその先にいる。
2. アキレスが亀の出発した地点に到達したとき亀がいた地点にアキレスが到達したとき、亀はその先にいる。
3. 以下永遠にこの繰り返しとなり、アキレスが亀に追い付くことはない。

話を簡単にするために、亀のスピードを秒速10cm、アキレスのスピードは秒速10mとし、ハンデは100mとする。 10秒後、亀は1m進み、アキレスは亀のスタート地点である100mのところまで進む。 0.1秒後、亀は1cm進み、アキレスは101メートルまで進む。 以下同様。

普通は数学的に解決する。 上の論証でアキレスが走った距離は 100+1+0.01+… という無限級数で表されるが、その和は有限でちょうど 10000/99 である。 かかった時間もその10分の1の 1000/99 と有限である。 従って論証は無限に続けられるが、アキレスが亀に追い付くのは有限の時間でできる。

量子力学的解決というのも思いついたのだがどうだろう。 上の議論を20回ほど繰り返すと、アキレスと亀の到達 位置の精度はプランク長さほどに縮む。 一方アキレスと亀の速度は一定と仮定しているので、不確定性原理から位置をそのような精度で得ることはできない。 従って、論証は破綻し、アキレスが亀を追い抜くことができる可能性がある。

# 多分名前があると思うけど

次のように定義される関数の値を求めたい。

• f(n,0) = f(0,m) = 1
• f(n,m) = f(n-1,m) + f(n,m-1)

n,m は自然数で、下の再帰は n,m > 0 で使う。

図形的に考えたければ、格子点 (0,0) から (n,m) までを右か上に向かって進む場合の数ということになる。

「値を求めたい」とか書いたが、具体的な値というより f(n,m) が閉じた形できれいに書けるのかが知りたい。 知られている結果だと思うし、多分名前があると思うけど、適当な本が手元にない。

追記(2008-02-22): これ、ただの二項係数だよ orz

# 数の話

実数というのは「現実」の「数」といった意味合いをもった名前である。 物理的な量(時間・長さ・面積・エネルギー)を表す数の体系として用いられるところを見ると、そう思えなくもない。 また、小学校で小数を習い、中学校で数直線との対応を教えられ、そのイメージは確固たるものがある。 しかし、これを数学的に厳密に扱おうとすると、意外と難しいところがある。

実数を定義する方法は色々あるが、普通はコーシー列というのを持ち出す。 有理数の列 {a_n} がコーシー列とは、任意の有理数 ε に対しある整数 N が存在して n>N ならば |a_n-a_N|<ε となることをいう。 このようなコーシー列全体を同値で割る(いい加減に言えば同じ収束先になるようなものは同じと思う)と、実数が出来上がる。

さて、いま「コーシー列全体」と簡単に言ったが、コーシー列は数えられないくらい沢山(数学の言葉で非可算無限)ある。 人間が不規則な無限の数列を全部想像し尽くすことはできないので、具体的に想像できるものは何らかの(有限の)規則があるものに限る。 そういうものは可算個しか存在しない、ということはほとんどの実数は実は想像の埒外なのである。 それでも実数は「現実」の「数」と言えるだろうか。

…

というような文で始まる数の体系についての文章をそのうち書く。

かもしれない。

# 算術的階層

最初に読んだときには使う機会があるとも思っていなかったのだが、 算術的階層(という言葉も憶えていなかったが)の記述を求めて久しぶりに高橋正子「計算論」を取り出す。 あまり大したことが書いていなかったので参考文献に挙げられていた廣瀬健「帰納的関数」を図書館で借りてきて(リンクは張ったけど絶版らしい)、関連する4章5章を読む。 こっちは凄く細かい。

思いがけないことが研究に繋がるんだなあ、と思うと同時に、もっと幅広く勉強しておくんだった、と珍しく反省してみたり。

# 不完全性定理

ゲーデル「不完全性定理」岩波文庫(2006)。 ゲーデルの論文の翻訳は最初の5分の1ぐらい。 残りは林晋/八杉満利子によるヒルベルトプログラムを中心にした解説で、あまりの長さにゲーデルの論文自体は忘却してしまいそうである。 それを読んでむしろヒルベルト以前に興味を抱いてしまった。

野崎昭弘「不完全性定理」ちくま学芸文庫(2006)。 こちらは10年ほど前に出た本の文庫化。 多分、元の本も読んだことがあるはず。 ユークリッドから話を始めて、素人向けにという感じ。

# ぼーっと考えたこと

n > 1 に対し、1/n < 1/(n-1)

ゆえに 1/(n^2) < 1/(n(n-1))

n が 2 以上のところ全て合計すると、ζ(2) - 1 < 1

差を考えると、1/(n(n-1)) - 1/(n^2) = 1/(n^2(n-1))

ふたたび最初の不等式から 1/(n^3) < 1/(n^2(n-1))

n が 2 以上のところ全て合計すると、ζ(3) - 1 < 1 - (ζ(2) - 1)

以降同様に考えると 0 < ζ(n+1) - 1 < 1 - (ζ(2) - 1) - ... - (ζ(n) - 1)

極限において 0 = 1 - Σ (ζ(k) - 1)

# ファイル圧縮

自然数の集合を扱うとき(たとえば素数表を作るとか)小さいうちはテキストファイルでも良いかとか思うが、そのうちに数一つ1ビットでいいわけだから…という方向に走る。 で、その先には圧縮という世界が待っているような気がするのだが、書き込みできる圧縮方式というのは存在するのだろうか。 つまり、数表全体をメモリーに保持できるぐらいなら始めから圧縮などしないので、圧縮された状態で生成していけるようなファイル形式、さらに言えば必ずしも前から生成されるとは限らないという想定で、既に圧縮した部分を書き換えられるようなものは?

あ、ファイルを分割しておけば良いのか。 分割を意識させないミドルウェアを作ればさらに融通が利きそう。

# サイクルのタイプ

スタンレイ「数え上げ組合せ論 I」の命題1.3.2に答えが書いてあった。 例の恒等式(恒等式?)の話である。

長さ n の置換を巡回置換(サイクル)の積に書いた時の、各巡回置換の長さを 1 がc₁個、2 がc₂個、…、n がc_n個と数え、それを (c₁,…,c_n) と並べたものをその置換のタイプという。 このとき次が成り立つ、というのが命題1.3.2である。

タイプが (c₁,…,c_n) である置換(∈S_n)の個数は n! / (1^c₁c₁! 2^c₂c₂!…n^c_nc_n!) に等しい。

したがって、それら全てを集めると n! に等しい。 問題にしていた式は、この等式を n! で割ったものであるから正しい。

# 恒等式? (2)

前回(恒等式?)のを証明しないまま、少し精密化の方向。 前回と同様 0 < b₁ < ... < b_r として、整数 n の分割を n = c₁ b₁ + ... + c_r b_r と書くことにする。 前回は
Σ Π (b_i^c_i c_i!)^-1 = 1
という n の分割全体に亘る和の式は恒等式だろうと主張した。 今回の予想は、この和をそれぞれの分割に関する Σc_i (つまり分割の因子数)の偶奇に従って半分ずつに分けると偶数部分の和・奇数部分の和それぞれが 1/2、というもの。 n は 2 以上。 2 から 6 まで確認した。

もちろん、今回のが示せれば前回の式は直ちに従う。 多分、どこかで誰かが証明してる結果だと思うんだけど、どこを探せばいいのやら。