数列と多項式の愛しい関係

自然数の有限数列 (ai)i=0n無限数列 (fi)i=0 を考える。

具体例:

(a0,a1,a2)=(1,1,1) (fi)i=0=(1,1,1,...,1,...)

これらの数列について、対応する多項式をつくる。 この作り方がどうして嬉しいのか、を説明しないのがこの文書の目的である。 えっ。説明はしないが、不思議な現象をお見せする。

正しいのか正しくないのか、その説明には様々な道具が必要になるので、 ページの長さの都合で全てを証明するわけにはいかない。 もしわからないところがあったら、間違っていないかどうか証明を試みてほしい。 ポイントで参照すべき資料を明示する。すべてというわけにはいかないけれども。

多項式の文字として zi を用いることにする。添字 i0 から までを動く。 たとえば、つぎのような多項式:

z0z1z2 Σi=0zi

を考える。自然数の有限長の数列は、zi のベキにならべる。これが、数列に対応する多項式である。

別の例をもちだすと、

(2,1,4)z02z1z24

という対応を考える。肩によっこいしょと乗せる感覚である。文字なので、 数字が重いとはちっとも思わない。 100 だって z0100 と、どんとこいである。 書き直すと、

Πi=0nziai=z0a0z1a1znan

という対応を考えている。

一方、無限列のときは、ベキに乗せるかわりに係数になってもらう。有限と無限は区別されるべきである。 というのは、半分冗談で、この原稿では、二つのお話を同時並行で紹介している。

(1,1,1,...,1,...)1+z+z2+z3++zi+

Σi=0fizii=f0+f1z1+f2z22+f3z33++fizii+

文字は数字とお友達なので、横にくっついて一緒に伸びていく。 肩に背負うときもあれば、並んで歩くこともあるのである。いいなあ、そういう関係。

無限列を多項式に変える方法は昔からよく知られている。

Σi=0fizii

は、 (無限)数列の母関数(generating function) という。いっぽう、肩に乗せるはなしはまだ名前がない。 仮の名前はあるんだけど、なじみやすい名前ではないので(HogeHugaMogeMuga)ここでは紹介しないでおく。

この二つの話題は、まったくといっていいほど共通点がない。にもかかわらず同じ文書で紹介するのは、 次の理由からである:

そして、整数計画と数え上げは「組合せ数学」という分野にひろがっている楽しい問題たちである。 多項式という共通の道具で、これらの問題を説明する、というのが、わたしの多項式に対する愛情である。 これは歪んだ愛情であるが、なにしろ大学を卒業する1年前から今にいたるまで、 うんぬんかんぬん年も愛でているのである。片思いなのはわかっているが、 振り向いてほしくて職までなげうったのだから(嘘です)、こうして文章に残しておきたい。

多項式の知られざる世界へようこそ。とはいえ、母関数のはなしは有名ですから、むしろ、 ぼくが母関数を知らなかったので、つまりこの文章は、あなたとわたしの両方が知らなかった世界なのです。 トワイライトゾーン。ゾーンっ

整数計画

ここでは、任意の整数計画問題をとりあげることはせず、特殊な形をした整数計画に注目する。 具体例として、つぎの toy example を通して整数計画を多項式の計算だけで行う方法を見よう。

計算機実験をした日が 2/14, 春の数学会が 3/20 からはじまるので、 あるのでということではないが、feasible solution を (2,1,4) に、 minimum solution を (3,2,0) にとるような整数計画問題を魔法ででっちあげる:

(221311)(x1x2x3)=(1011)

x10,x20,x30

この二つの平面の交わりの直線のうえ、ただしすべての成分が非負成分であるような点のなかで、 あるベクトルとの内積を最小にする問題を考える。 このような問題が整数計画だと思っていただいてよい(というか、この例以外に文章のなかにでてくるものはない)。

実際の整数計画問題は、より条件がユルいのであるが、今回はパズル的性格のつよい具体例を紹介している。

左辺の行列の成分は、1,2,3 のどれか、 右辺のベクトルは 0,1 のどれかしか用いないという無駄な制約で問題を作成した。 このような数字の制約は整数計画とは関係なく、たんに問題を面白難しくしたい取り組みである。

整数計画問題は、左辺の行列、右辺のベクトル、そして、 最小にするような内積ベクトルを与えて決める、整数成分からなる線形代数のようなそうでないような問題である。

どのようなベクトルとの内積を最小にするか。たとえば、

(128,64,1).(x1,x2,x3)

のように適当にえらぶと、最小解は既存のアルゴリズムですぱっと求まり、 (1,0,8) となる。 しかし、このような方法で適当にえらんでいたのでは、数学会の日程 (3,1,0) を最小解にするベクトルなど、 永久(とわ:108)にみつからないのである。

計算はめんどうなので、計算代数 Octave にやらせる:

% An octave session
A = [ 2, 2, 1 ;
      3, 1, 1 ];
b = [ 10, 11 ];
c = [ 128, 64, 1 ];
% lower bound
lb=[ 0, 0, 0 ];
% unset upper bound
ub=[];
% standards
ctype="SS";
% integer variables
vartype="III";
% computing
glpk(c, A, b, lb, ub, ctype, vartype)
%==> the minimum solution (1, 0, 8)

One, Two, Three

もう、読者はついてきていない頃だろうが、そう思って安心して、的であるところの 3/20 を最小解にするような、 内積をあたえる整数ベクトルに登場してもらう、それは:

(1,2,3)

である。ためしに、さきほどの Octave の計算で c=(1,2,3); に変えてもらえば、 計算 glpk の結果が (3,2,0) になるのがわかる。

じつは、これだけでは話がおわらない。異なる値で、左から順にどんどん大きくなるように数字をならべると、 そういうベクトルでは常に最適解が (3,2,0) となるように問題が作られているのである。

な、なんですって。つまりこういうことである、 (1,2,3) を最小とする内積を考えても、 (1,10,100) を最小とする内積を考えても、最小解は (3,2,0) となるのである。より一般的に、

(c1,c2,c3):0c1<c2<c3

のような、ベクトルとの内積を最小にする解は (3,2,0) なのである。証明は可能。

整数計画問題を多項式に翻訳できるひとは、計算代数を片手にとれば、このような小細工など朝飯前。 いや、多少の運はあったと思われる、バレンタインデーとか組込むことができたのは幸運も作用した。

このはなしは、整数計画の逆転裁判である。ふつう、整数計画では、 方程式と内積をとるベクトルが与えられ、その条件下でどのようにして解を求めるかを競う。

しかし、多項式に愛情をそそぐヒトは、どのような行列とベクトルを用意すれば、 狙った点を最小解にすることができるか、という問題のほうが面白いと思うのである。

ここまで読むのについてきたひとは、えらいっ(たけし)。

二項式の世界へようこそ

こんなげーむにまじになっちゃってどうするの、という話をこれから展開する。 母関数についての情報を求めているひとは、すっとばして二つ目の話題に飛んでいただいて構わない。 でも、そちらのほうは当たり前の話だし、ぼくが知らなかったからって理由で書いてるから、 けっきょくどちらもつまんないねってことになると思う。 基本的にこの文章は他人に読んでもらうことを考えていない。

ゲームの構成には、多項式を用いた。冒頭で説明してみたように、有限長の自然数ベクトルは、 文字の肩にならべることにより、多項式に翻訳される:

z13z22z30=z13z22

これは、+ の文字があらわれない多項式で、特別に単項式(monomial)というなまえがついている。 モナドとは残念ながら関係がまったくない。

このゲームを開始した日、2/14 もこの調子で monomial に変換してあげる:

z12z21z34=z12z2z34

これらをペアにして問題を作成したのだが、そのペアは多項式の世界でこう書く:

z12z2z34-z13z22

ふたつの monomial が - を間にはさんでペアになっている。 このような多項式を特別に二項式(binomial)という。 整数計画のはなしでは monomial と binomial が中心的な役割を果たす。三角関係以上のものはあらわれない。

この二項式が生成する多項式のイデアル構造から、今回の問題の 2×3 行列を導出した、 というのが最初の種明かしである。方法は教科書通りなので、あえて書くことはしなくてもいいだろう。 どちらにせよ、もうあなたは眠りかけているのだし。ちがいますか。 なんと、まだついてこられるというのは、辛抱強いのか、そもそも種を知っていてつきあって下さっているのか。

よいでしょう、この次はすこしまじめになります。

Conti-Traverso のアルゴリズム

まじめになりましょう。Google で “Conti Traverso” と検索すると、 じつに多種多様な整数計画問題のペーパーがでてくるとおもいます。

いけがみの知る限り、整数計画と多項式をむすびつけた画期的な発想は、 Pasqualina Conti 氏と Carlo Traverso 教授の 1991 年の論文にあります:

Buchberger アルゴリズムとは、多項式のイデアルの Gröbner 基底を計算するアルゴリズムであります、説明略。

出た当初は、このアルゴリズムを最適化すれば、整数計画が多項式時間で解ける、 となると P=NP が証明できる方法かもしれない、と思われましたが、ざんねんながら予想は否定的です。

というのも、さきほど紹介した二項式の計算を駆使しても、既存の方法では上から doubly exponential だろう、 いや、もう tight に決まったのかな、まあ知りませんが、とにかく遅いです。 有名でない理由はその辺にあるのかもしれません。

Conti-Traverso アルゴリズムの概要は、つぎのように言うことができます:

  1. すべての feasible solution にたいして、それらの間をうつりまわるような遷移をつくる
  2. その遷移は、二項式、つまり数値ベクトルのペアである。これらが、とあるルールで書き換えられる
  3. 書換えは合流する
  4. 書換えは停止する、さらに停止した数値ベクトルは feasible かつ minimal optimum である

どういうことかというと、まずひとつ feasible solution をえらび、このルールを生成しさえすれば、 あとはルールにしたがってどんどん書き換えるだけでいつか必ず停止し、そのベクトルは整数計画の解なのです。

まるで、受理するまでどんどん文字を食べるオートマトンみたいですね。 停止性が保証されているので安心して食べてください。

この文章で書こうとしているように、整数計画問題の数理的構造を多項式で説明できるという着想はあたらしく、 いまだに僕のように周辺をしらべまわっているニンゲンがいるくらいです。ニンゲンは本当にいろいろいる。

toric ideal

ですます調おわり。整数計画問題は Conti-Traverso アルゴリズムを出発点として、 代数幾何学の一派であるところの、 toric ideal と結びつくのである。 はたまた Google していただきたい。

toric ideal と、組合せ数学との融合についての多面的な紹介が pantodon にある:

どうでもいいが、わたしの D 論では整数計画の線形連立方程式を mod 2 で解きましょう、という話で、 キモはつぎの二項式、つまりベクトル間のルールである:すべての i と変数 zi について

zi2-1

これは、ベクトルで言うと、

(...,2,...)(...,0,...)

すべての i の位置にある 20 になるという規則、すなわち mod 2 なのだ。 誰でも気付くだろこんなの、という話だが、誰もやってなかったのでわたしがいただいた。 (実際には、これをいれることで新たな技術的な困難が発生し、それを乗り越えなければなりません)

mod 2 の世界では、toric のような綺麗な幾何構造が破壊されてしまい、 くるくるまわる同値類が世界のなかにあらわれるので、わたしの勝手で、toric 鏡の国と呼んでいる。 この国であそぶのはとてもたのしい。

計算機実験

話を戻して Conti-Traverso アルゴリズムを、このたびの問題に適用する。 教科書通りのアルゴリズムを Singular で行う。

// Singular session
ring r=0,(w(0..1),z(0..2)),(a(1,1,0,0,0),a(0,0,1,2,3),dp);
ideal I=w(0)^2*w(1)^3-z(0),w(0)^2*w(1)-z(1),w(0)*w(1)-z(2);
ideal J=groebner(I);
poly f=w(0)^10*w(1)^11;
reduce(f,J);
//===> z_1^3 z_2^2

やっていることは以下の通り(多項式順序についてはまだ説明をしていない):

  1. 標数 0 の係数体で、変数 w0,w1,z0,z1,z2 の環を定義する、また、多項式順序を付ける
  2. イデアル I を行列からきめる:行列の各行に w、各列に z を対応させた二項式でイデアルを生成する
  3. イデアル I の Gröbner 基底をもとめ、それを J とする
  4. 右辺ベクトルに対応する単項式を w でつくる:f=w010w111
  5. f をグレブナ基底 J で 1. で決めた項順序のもとで正規形を計算する。

答は単項式 z03z12 となり、めでたく (3,2,0) を得る。なんでこんなことがうまくいくかというと、 Conti-Traverso の論文の解説になってしまうので、ここでは文章を割かない。

重みベクトルについてだが、それは説明していない多項式順序というものに関係している。 各文字 z0,z1,z2 について、文字の偉さを z0<z1<z2 に重み付け (1,2,3) で与えている。 これは、整数計画問題の内積にもちいたベクトル (1,2,3) から決めている。 多項式順序の定義はややこしいうえに、読んでも最初はぴんとこないので説明しない。

重みベクトルのふしぎ

(c1,c2,c3):0c1<c2<c3

のような、ベクトルとの内積を最小にする解は (3,2,0) なのである。の、謎解き。

Conti-Traverso アルゴリズムを、まだ説明していない toric ideal に焼き直して計算する。

Singular は toric.lib を持っているので、それにおねがいする。

// Singular session
LIB "toric.lib";
ring r=2,z(0..2),dp;
intmat A[2][3]=2,2,1,3,1,1;
ideal I=toric_ideal(A,"ect");
ideal J=groebner(I);
// we know (2,1,4) is feasible but not optimal
poly f=z(0)^2*z(1)*z(2)^4
// get the optimal solution
reduce(f,J);

整数計画問題の右辺の行列に対する、逆辞書式多項式順序のグレブナ基底は、 上にあげた計算機実験により、

z0z1-z24

となる。多項式順序として z0<z1<z2 を与えると、 この二項式の偉い項は後ろの単項式 z24 になる。

そこで、feasible solution (2,1,4) に対応する単項式 z02z1z24 を、項書換えしてみる。 つまり、z24z0z1 に置き換える。 これはさきほどの二項式の偉さ関係からでてくる書換えルール。 書換えにより z24 はあっさり消え、 z03z12 つまり (3,2,0) がでてくるのである。

チェス板をひっくり返して、どのようにして feasible solution (2,1,4) から minimum solution (3,2,0) を出すかというと、このように

z0z1-z24

を Gröbner 基底とするような toric ideal はなにか、そしてそれに付随する行列は?という問題を、 解けばいいということを多項式を愛する人々は知っているということである。

すべては謎のまま

手品師は種を明かすことはないが、種本はつねに存在する。読者はいまや、整数計画と「組合せ数学」、 特に種本であるところの『代数幾何と可換代数におけるグレブナー基底の有効性』を手に取り、 夕方どきに計算用紙を埋め尽くして、暇をもてあますことがなくなることを筆者は予言する。 なお当たったためしはない。

母関数

整数計画と有限長の自然数ベクトルと多項式のはなしは終わり、つぎの話題は無限長のベクトルにうつる。

この章では『離散体積計算による組合せ数学入門』(参考文献リスト参照)の最初の一コマから、 具体例をいただいた。ここには、Fibonacci 数列の話題が載っている。

Fibonacci 数列の話にはいるまえに、まず、もっと簡単な具体例から見てみることにする。

母関数の具体例

つくりかた:

無限数列

(fi)i=0=(f1,f2,f3,...,fi,...)

に対応する無限級数をつぎのようにつくる。

Σi=0fizii=f0+f1z1+f2z22+f3z33++fizii+

ひとつめ:

(1,1,1,...,1,...)1+z+z2+z3++zi+

からみてみよう。数列にあらわれる数字はすべて 1 なので、係数はすべて 1 となる。 この数列は、初項と公比がともに 1 の等比数列である。

あまくだりではあるが(でたよ) i が自然数をうごくとき、

(1-z)(1+z+z2+z3++zi)=1-zi+1

であることを、i の数学的帰納法によって示すことができる。このことから、

1+z+z2+z3++zi+=1/(1-z)

という簡潔にして閉じた式を得る、ただしこの上の式は z が複素数でかつ z<1 のときにのみ等号が意味を持つ。

ここで、この話を初めて目にした読者は、いくつもの疑問を持たねばならない: 疑問には二種類あって、まずこの文書が対象とする疑問を列挙する:

  1. あまくだりとか言うが、その式はどこからでてきたのか
  2. z が複素数だというが、なぜそうするのか
  3. z<1 のときに等号が意味をもつとはなにか
  4. 無限数列をあたえたとき、いつでもそのような閉じた式を得ることができるのか
  5. 閉じた式の、等号が意味をもつための半径とはなにか

答えるまえに、おもいつくであろう、もう一方の種類の疑問はこの文書では答えないことを明記する:

このような議論は、中世においてすでに行われており、文を割くことはしない。

その式は空から降ってくるのか

(1-z)(1+z+z2+z3++zi)=1-zi+1

はどこから降ってくるかというと、等比級数の和の公式という、高校の数学の教科書をよく振ると、 落ちてくるものである。押し入れのなかに眠っている諸君は振ってみればよろしい。

複素数は便利ですね

両辺を 1-z で割るなどという危険な操作をしてよいわけがない。 安全装置として、複素数というものが存在するのである。まだ悩む諸君は ε-δ をみっちり議論せよ。

等号が意味をもつとはなにか

等号がいつでも成り立つとおもう諸君は、自らの不明を恥じなければならぬ。 人生とはいつも平坦ではない。

違う数列を考えたくなるのが人間

都合のよいものと都合の悪いものをしらべるためには、まず独創性を高めるべきである。 でたらめに無限数列を考えるのは自由なので、その数列にたいしてルールを適用し、 閉じた式をつくる努力をしてみるのは、まさに自由の行使であり、諸君はその権利を有する。

閉じた式と級数との等号条件のあやういバランス

級数の収束半径というキーワードのもとで、諸君の知識はいやおうに高まるであろう。 収束半径の判定法なども学んでみるとよい。なお、いじわるなことに、 公比 1 というのは判定法などという抜け道が通用しない具体例になっている。

判定法があるという直感をもつためには、まず次の数列と母関数を考えてみよう:

(1,1/2,1/4,....,1/2i,...)Σi=01+z/2+z/4++z/2i+

長さ 2m の物差しを目の前にして、左でも右でも好きなほうから、1m をとり、のこりから 1/2 m = 0.5 m をとり、 という操作をくりかえし、なにが残るのかを、カタツムリのごとくじわじわやれ。 抽象的な証明などはあとからでよろしい、というのが筆者の主張である。

ひどいことに、直感と証明との温度差を感じるということができるのも特徴である。甘さよりも苦さ。

Fibonacci 数列

等比数列ふたつ(公比 11/2)も具体例をみたので、十分だという向きのために、 もうひとつ具体例をささげる。この Fibonacci 数列の例は、 『離散体積計算による組合せ数学入門』の第一章第一節をかざっているので読めばよろしい。

この文書では剽窃を避けるために、教科書に載っていない式変形をずらりとならべて、 おいしい思いをする(筆者が)。

Fibonacci 数列の第一項が 0 であるか 1 であるかは、常に紛糾する話題であり、 ここでは教科書から離れるべく初項を 1 ととる、すなわち:

1,1,2,3,5,...,fi+2=fi+1+fi,...

を考える。等号をひどいことに用いているが、 ようするに i+2 番目は i+1 番目と i 番目をよく見て決めなさいということである。 なにが、「ようするに」であるか。

Fibonacci数列、初項が 1 の母関数を考えよう。

1+z+2z2+3z3+5z4++(fi+1+fi)zi+2+

この式について閉じた式があるのか。それは、

1/(1-z-z2)

である。証明はしない。 定義にもどって、混乱なく計算すれば、この式がでてくる、はずである。 筆者は 2 回ほど間違えたあげく、初項が 0 のときの式をまずつくった。

母関数は、数列の閉じた式を知らずとも閉じた式をつくることができるのである: というのは言い過ぎていて、あくまでも場合による。

z=0 のまわりで Taylor 展開してみる。

/* a maxima session */
(%i1) f:(1 / (1 - z - z^2));
                                      1
(%o1)                           ------------
                                    2
                                 - z  - z + 1
(%i1) taylor(f,z,0,7);
                      2      3      4      5       6       7
(%o1)/T/  1 + z + 2 z  + 3 z  + 5 z  + 8 z  + 13 z  + 21 z  + . . .

たしかに、係数は Fibonacci 数列(初項1)の形をしている。あくまで i=7 までしか確認していないが…

この文書の最終目的である、なぜ無限数列を考えるときに、母関数という多項式をつくるのか、 の具体例として Fibonacci 数列(初項 1)をしらべることにする。これは魔術である。

1+(z/(1-z-z2))

の式変形のトリックを行う。この式から 1 をひいた別の式について:

z/(1-z-z2)=1/51-(1+5/2)z-1/51-(1-5/2)z

である。手計算をがんばる、あるいは右辺を数式処理で計算して確かめるとよい。筆者は手計算をまちがう。 中学のときにならう、二次方程式の解の公式をつかうと楽である。覚えているかな?忘れていましたよ。

/* another maxima session */
(%i1) g:(1/sqrt(5))/(1-((1+sqrt(5))/2)*z) - (1/sqrt(5))/(1-((1-sqrt(5))/2)*z);
                       1                               1
(%o1)   ----------------------------- - -----------------------------
                      (sqrt(5) + 1) z                 (1 - sqrt(5)) z
         sqrt(5) (1 - ---------------)   sqrt(5) (1 - ---------------)
                             2                               2
(%i2) factor(rat(g));
                                       z
(%o2)                           - ----------
                                    2
                                   z  + z - 1

ただしいようである。つぎに、この差の左と右に注目する。最初の具体例

(1,1,1,...,1,...)

に対応した母関数

1+z+z2+z3++zi+=1/(1-z)

の右辺の z に、z=1+52t, z=1-52t のふたつを代入して、 t の式として変形しなおす計算をいやがらずにやりなさい。

t の式の係数と z の式の係数を比較することにより、Fibonacci 数列(初項 1) の閉じた式

fi=15(1+52)i+1-15(1-52)i+1

を得る。計算はとてもめんどくさい。が、やらねばならぬ。この公式は

と呼ばれている。

以上の魔術は、ある種の一般性をもつ: すなわち、無限数列の閉じた式を知りたいとき、母関数をつくり、母関数の閉じた式をつくり、 トリックを用いて、最後に係数を比較するという方法で閉じた式がでてくる、ことがある。

手品師は種を明かすことはないが、種本はつねに存在する。読者はいまや、数え上げと「組合せ数学」、 特に種本であるところの『離散体積計算による組合せ数学入門』を手に取り、 雨の日の週末に計算用紙を埋め尽くして、暇をもてあますことがなくなることを筆者は予言する。 なお当たったためしはない。

まとめ

この文書に書いたことはなにひとつとしてオリジナルな技術はない。 以下に並べた参考文献を読めばわかることだらけである。 この文書にある数学的な誤りやそのほかの誤りは筆者のいけがみに由来するものであり、 あなたは批判する文書を書くという自己満足をしてもいっこうに筆者の怒りをかうことはない。 筆者は自らがずぼらであるという認識を持っており、他者からの批判については、 目の前で言われない限りはネットワーク上の人格など頭から否定している旧いニンゲンなのである。

なんちゃって。

©2011 IKEGAMI Daisuke

References

整数計画参考文献

母関数参考文献