113

第5章

グレブナ扇と Tropical Geometry

この章で使うソフトウエア: R, 4ti2, C 言語, Asir, gfan, polymake, sm1

Todo: video://korea-tropical にプログラムのデモも加えて講義. この章は手書きノートによる.

5.1

Polytope と polymake の “いろは”

Polytope, Polyhedron, facew (P ), Normal fan の詳しい導入.
数学関連事項はテキスト以外に板書でも説明. ビデオ: 2005-05-30 参照.

polymake の作者についてなど.
数学関連事項はテキスト以外に板書でも説明. ビデオ: 2005-05-30 参照.
New(f ) の計算には点の集合の凸包の計算が必要となる.
例 5.1 点の集合の凸包を計算し, その facet の法線ベクトルを計算せよ.

Polymakepolymake では, 入力点は原点をとおらない超平面の上においておく必要がある. 下の例では x1 = 1に点をのせてある. このファイル名を p-conv0.txt とする.
¶

Et/p-conv0.txt³

POINTS
1 0 0
1 2 0
1 0 3
1 1 1

µ
polymake p-conv0.txt FACETSと入力することにより, 次の出力ファイル (同じ名前の出力 p-dim.txt) Et/p-conv.txt

´

114

第5章

グレブナ扇と Tropical Geometry¶³_application polytope_version 2.2_type RationalPolytope
POINTS
1 0 0
1 2 0
1 0 3
1 1 1
FACETS
0 1 0
3 -3/2 -1
0 0 1
AFFINE_HULL

µ
´
を得る.
アルゴリズムについての覚え書き. 2 次元の凸包. Edelsbruner の coloring algorithm [?]. G.Zieglerの本 [2] V 表現と H 表現の変換. Fourier-Motzkin algorithm. CDD ライブラリ [3] およびアルゴリ
ズムの説明.

CDD ライブラリのアルゴリズムの詳細については, [3] の論文 “Double description revisited” を参照.
次元の計算. このファイル名を p-dim.txt とする. Et/p-dim0.txt¶
POINTS
1 0 0 31 2 0 31 0 3 31 1 1 3µ³´polymake p-dim.txt DIMと入力することにより, 次の出力ファイル Et/p-dim.txt¶³_application polytope_version 2.2_type RationalPolytope
POINTS
1 0 0 31 2 0 31 0 3 31 1 1 3
DIM
2

µ

´

を得る.

Volume を計算するには
polymake p-dim.txt VOLUMEが必要. 計算には三角形分割が必要.
数学関連事項はテキスト以外に板書でも説明. ビデオ: 正則三角形分割, Depthlaunay, voronoi など, 2005-05-30

5.2. 単独方程式の Tropical zero set

5.2

115

単独方程式の Tropical zero set

gfan
Todo: gfan の作者について.
gfan では initial term を weight と exponent の内積との最大値で定義している. われわれのノー
トとは反対になっているので注意しよう.
例 5.2 われわれの running example である

I = (x1 + x2 + x3 )の tropical zero set を gfan で計算してみよう.
入力プログラム (t3.txt) Et/t3.txt¶³{a+b+c}µで生成されるイデアルの tropical zero set を計算してみよう.

´gfan への入力. Et/t3.sh¶³

gfan_tropicalstartingcone <t3.txt | gfan_tropicaltraverse >t3-out.txtµ´

出力 Et/t3-out.txt¶³

Ambient dimension: 3
Dimension of homogeneity space: 1
Dimension of tropical variety: 2
Is simplicial: true
Order of input symmetry group: 1
Number of maximal cones: 3
Modulo the homogeneity space:{(1,1,1)}Rays:{
0: (-1,0,0),
1: (1,1,0),
2: (0,-1,0)}
Printing index list for dimension 1 cones:
{
{0},
{1},
{2}}
Number of dimension 1 cones incident to each ray:
(1,1,1)
F-vector:
(3)

µ

´

手計算のとおり 3 本の ray がある.

5.3

グレブナ扇

I を同次イデアルとする. 二つの weight vector w と w0 が同値 w ' w0 であることをinw (I) = inw0 (I)

(5.1)

第5章

116

グレブナ扇と Tropical Geometryで定義する. w と同値な weight vector を集めたものを w できまる Gröbner cone とよび, C(w) と書く. あい異なる C(w) の閉包を集めたものが Gröbner fan Ē(I) である.

I = hf i のとき, I の Gröbner fan は f の Newton 多面体の normal fan に他ならない.
例 5.3 次の頂点を持つ多面体の normal fan の第一象限の部分を図示せよ.

(0, 0, 0), (2, 0, 0), (1, 1, 0), (0, 3, 0), (5, 5, 5), (0, 0, 1)
第一象限の部分のみなら, 同次式である必要はない.

gfan
gfan は tropical zero set の計算もできるが, Gröbner fan の専門計算システムとしてすぐれている. (gfan は sage ととも昨年 (2006 年) 脚光をあびた新しいソフトである)
Et/g-n.txt¶³{1+a^2+a*b+b^3+a*b*c+c}µ
入力コマンドは Et/g-n.sh¶´³

gfan <g-n.txt | gran_render >g-n.xfig
xfig g-n.xfig

µ

´

例 5.4

I = (x1 + x2 + x3 , x2 + 2x3 )の Gröbner fan を計算せよ. 結果を図示せよ.

gfan
入力ファイル Et/g-l2.txt¶³{a+b+c,b+2*c}µ
最大次元の cone は 3 つある.
図の生成コマンド (g-l2.sh はなにも描かない. 何故か?) Et/g-l2.sh¶´³

gfan <g-l2.txt | gfan_render >g-l2.xfig
gfan <g-l2.txt | gfan_renderstaircase -m >g-l2-s.xfigµ´

xﬁg での図を見るには, xfig コマンドを用いる.
少々美しい図を生成する例を紹介しておこう. (A.Jensen 自身による紹介プログラム) Et/sym.txt¶³{aab-c,bbc-a,cca-b}{(1,2,0)}µ´

Et/g-sym.sh¶³

gfan <sym.txt | gfan_render >sym.xfig
gfan <sym.txt | gfan_renderstaircase -m >sym-s.xfigµ´

5.3. グレブナ扇

117kan/sm1
Kan/sm1 は asir と同様国産のシステムである (実は筆者が著者). Kan/sm1 では/usr/local/OpenXM/lib/sm1/gfan.sm1 にある入力例を参考に入力を用意し, 実行する.
sm1 をスタートしたあと,(gfan.sm1) run ;cone.sample ;(なお sm1 では 空白は token の分離に用いるので ;1-simplex × 2-simplex に付随した aﬃne toric varietyの前に空白の入力が必要) と入力すると,I = (x1i x2j − x1j x2i | 1 ≤ i < j ≤ 3)の Gröbner fan を計算するデモを実行する.
専門家向け: gfan.sm1 に付属の cone.sample2 の方は y と y − (x − 1)2 に付随する Bernstein-Sato
多項式を Rouchdi Bahloul のアルゴリズムで計算するため, 微分作用素環のイデアルの local Gröbner

fan の制限を計算する例である.
gfan と同様な次の問題をやってみよう.
例 5.5

I = (x1 + x2 + x3 , x2 + 2x3 )の Gröbner fan を計算せよ.

Et/s-l2.sm1

118

第5章

グレブナ扇と Tropical Geometry¶³[(parse) (gfan.sm1) pushfile] extension/mytry {%決まり文句
cone.load.cohom/cone.ckmFlip 1 def% 変数のリスト (形式 1)% List of variables/cone.vlist [(a) (b) (c)(Da) (Db) (Dc) (h)] def% 変数のリスト (形式 2)/cone.vv (a,b,c) def% 3 変数なので 3 3 と書く.
/cone.parametrizeWeightSpace {3 3 parametrizeSmallFan} def% 以下は同次多項式の場合はきまり文句として書いておく.
/cone.type 2 def/cone.local 0 def/cone.w_startnull
def/cone.h0 1 def% 入力はここへ書く.
/cone.input[(a + b + c)(b + 2 c)]def% 以下は同次多項式の場合はきまり文句として書いておく.
/cone.DhH 0 def/cone.gb {cone.gb_Dh} def
cone.input message%%%% Step 1. Enumerating the Grobner Cones in a global ring.
%%%%
The result is stored in cone.fan
getGrobnerFan%%%% If you want to print the output, then uncomment.
printGrobnerFan} defµ
このファイル名を s-l2.sm1 とするとき, sm1 をスタートしたあと,(s-l2.sm1) run ;mytry ;
で計算を遂行する.

D-加群についてのグレブナ fan を調べようとおもったら現在のところ kan/sm1 しか実装がない.
Todo: D-module の節で x2y2.sm1 を説明.

´

5.4. tropical geometry

5.4

119

tropical geometry

gfan では initial term を weight と exponent の内積との最大値で定義している. われわれのノー
トとは反対になっているので注意しよう.
例 5.6

I = (x1 + x2 + x3 + x4 , x2 + 2x3 + 3x4 )の tropical zero set.

gfan への入力例を紹介しよう. たとえば次の入力プログラム (t42.txt) Et/t42.txt¶³{a+b+c+d,b+2*c+3*d}µで生成されるイデアルの tropical zero set を計算してみよう.
gfan への入力. Et/t42.sh¶´³

gfan_tropicalstartingcone <t42.txt | gfan_tropicaltraverse >t42-out.txtµ
出力 Et/t42-out.txt¶´³

Ambient dimension: 4
Dimension of homogeneity space: 1
Dimension of tropical variety: 2
Is simplicial: true
Order of input symmetry group: 1
Number of maximal cones: 4
Modulo the homogeneity space:{(1,1,1,1)}Rays:{
0: (-1,0,0,0),
1: (0,-1,0,0),
2: (1,1,1,0),
3: (0,0,-1,0)}
Printing index list for dimension 1 cones:
{
{0},
{1},
{2},
{3}}
Number of dimension 1 cones incident to each ray:
(1,1,1,1)
F-vector:(4)µ´
Homogenity space が (1, 1, 1, 1) なので, (1, 1, 1, 1) のスカラー倍を足したものは同値な weight となる. q ≥ 0, p ∈ R としてq((−1, 0, 0, 0) + p ∗ (1, 1, 1, 1))q((0, −1, 0, 0) + p ∗ (1, 1, 1, 1))q((1, 1, 1, 0) + p ∗ (1, 1, 1, 1))q((0, 0, −1, 0) + p ∗ (1, 1, 1, 1))

第5章

120

グレブナ扇と Tropical Geometryの 4 つが tropical variety の最大次元の cone である.
たとえば w = (1, 1, 1, 0) と時,I = (x1 + x2 + x3 + x4 , x2 + 2x3 + 3x4 )の reduced Gröbner basis を Âw で計算すると

G = [x1 − x3 − 2x4 , x2 + 2x3 + 3x4 ]となる.

inw (I) = (x1 − x3 , x2 + 2x3 )はたしかにモノミアルを含んでいない.
なお現在の gfan では, tropical zero set の次元が 1 となる場合は abort と表示されて停止してしまう.
例 5.7 gfan のソースの doc/example にある grassmann2 5 をためしてみよう.

Et/grassmann2x5.txt¶³{
bf-ah-ce,bg-ai-de,cg-aj-df,
ci-bj-dh,fi-ej-gh}{(3,6,8,9,0,1,2,4,5,7),(0,6,5,4,3,2,1,9,8,7)}µ´(m + 1) × n 行列を考える. i1 , . . . , im , jk 列をならべてつくった正方行列式を pi1 ···im jk と書くとき, Plücker の関係式は

m+1∑(−1)k pi1 ···im jk pj0 ···ĵk ···jm+1 = 0

k=0

と書ける.
いまの場合 m = 1, n = 5 である. ちなみに asir でこのような関係式の具体形を出力したい場合
は, Et/asir-plucker.txt¶³

plucker_relation([1],[2,3,4]);plucker_relation([1],[2,3,5]);plucker_relation([2],[3,4,5]);µなどと入力する.

gfan への入力は Plucker 多項式である.
である.

´
(5)
2

= 10 なので 10 変数ある. 10 − 3 の 7 次元の variety

出力をみればわかるように, 同次な部分が 5 次元分あり, tropical zero set の実質的な部分は 2 次
元である.

Grassmannian の tropical 幾何の理論的考察については, David Speyer, Bernd Sturmfels, The
Tropical Grassmannian, http://arxiv.org/abs/math/0304218 (arXiv:math/0304218v3) [5] を参照.
とくに G2,n の tropical zero set の simplicial complex としての構造は phylogenetic tree というgraph に等しいということが証明してある.

5.4. tropical geometry121

問題: 筆者は証明を読んでいないので解読してレポートされたい. あわせて gfan で G2,6 の場合のグラフを作成されよ.
超幾何関数へのノート: (2, 5) Grassmann は Appell の 2 変数超幾何関数 F1 に関係深い.

第5章

122

5.5

グレブナ扇と Tropical Geometry

Toric variety

この節では toric variety のグレブナ基底とそれに付随する多面体の組み合わせ論を Macaulay や

4ti2 などを利用してしらべていくことにしよう.
Macaulay2 は可換環論や D-加群の計算を行う以外に非常に美しいユーザ言語も付属しているシステムである.

5.5.1

Macaulay2 の基本

まず Macaulya2 を対話型電卓として利用する方法を説明する.
Macaulay は数の処理のみならず, 多項式の計算や環論の不変量の計算もできる. 電卓的に使うための要点を説明し例をあげよう.
例 5.8 +,-,*,/,^ はそれぞれ足し算, 引き算, かけ算, 割算, 巾乗. たとえば,

2*(3+5^4)と入力すると 2(3 + 54 ) の値を計算して戻す.
例 5.9 多項式の計算をするにはまず環の定義をする. それから計算する.
¶³

i3 : R = QQ[t,x,y,z]o3 = Ro3 : PolynomialRingµ´
ここで R : PolynomialRing は R が PolynomialRing オブジェクトであることを示している. Rと入力すると R と PolynomialRing と戻るのみである. このように Macaulay 2 では 変数名と入力しても値が戻るとは限らないことに注意. R の中身を詳しく見るには, describe(R) または

describe R コマンドを用いる.
一般に Macaulay 2 では, 変数とすると, 値 :な場合は適宜簡潔な表現方法が選択される.

オブジェクトの名前 を表示するが, 値が複雑

5.5. Toric variety

123

¶

³

i6 : f=x-t^22o6 = - to6 : R+ x

i7 : g=y-t^33o7 = - t+ yo7 : R
i8 : h=z-t^44o8 = - t
o8 : R+ z

i9 : f+g3
o9 = - t - t
o9 : Rµ
この例では ...

2
+ x + y例 5.10 さて前の例で定義した多項式 f, g, h から t を消去してみよう. 消去は t 変数の重みを 1 に,他の変数の重みを 0 としてグレブナ基底を計算することにより実行できる.

´

第5章

124

グレブナ扇と Tropical Geometry¶³

i12 : R = QQ[t,x,y,z, Weights => {{1,0,0,0}}]o12 = Ro12 : PolynomialRing
i13 : f=x-t^2; g=y-t^3; h=z-t^4;
i16 : curve=ideal(f,g,h)2
o16 = ideal (- t3
+ x, - t

4+ y, - t+ z)

o16 : Ideal of R
i17 : gb(curve)o17 = | y2-xz x2-z tz-xy ty-x2 tx-y t2-x |o17 : GroebnerBasisµ´

この結果をみればわかるように

y 2 − xz, x2 − zが t を消去して得られる多項式であり, その幾何的意味は ... まだ書いてない
さて Macaulay2 ではさまざまな環論の不変量を計算するための関数があらかじめ組み込まれている.
例 5.11 上の curve の (Krull) 次元を計算せよ.
¶³

i18 : dim curve
o18 = 1
i19 : degree curve
o19 = 4µ´
なお 上の dim curve は dim(curve) と書いてもよい. また 上の degree curve は degree(curve)と書いてもよい.
例 5.12 モノミアルで生成されるイデアルの極小自由分解の計算をしてみよう. この機能により組み合わせ論と可換環論の交錯する魅力的な分野での数学実験が可能となる.

5.5. Toric variety

125

¶

³

i20 : S=QQ[a,b,c,d];i21 : I=monomialIdeal(a^2,a*b,b^3,a*c);o21 : MonomialIdeal of S
i22 : res I
1

4

4

1

o22 = S

<-- S

<-- S

<-- S

<-- 0

0

1

2

3

4

o22 : ChainComplexµ´

上の 1, 4, 4, 1 を betti 数とよぶ. betti 数に関する数学の定理... まだ書いてない

5.5.2

Macaulay2 を用いて多面体を三角形に分割する

Todo: 正則三角形分割と toric ideal の initial については黒板で説明.
課題: 論文 2007/knx/st.pdf [12] を読み証明を理解する.
ここでは図 5.5.2 に表示された 5 点を考える. この 5 点の凸包は四角形 1,2,3,4 であるが, この 5点とその重み (1, 1, 1, 1, 0) を用いた正則三角形分割を計算してみよう.

y2
3

4

5
1

2

y1

第5章

126

グレブナ扇と Tropical Geometry¶³

i1 : load "LLL.m2";
i2 : load "triangulate.m2";--loaded triangulate.m2
i3 : A={{1,1,1,1,1},{0,2,0,3,1},{0,0,2,2,1}}o3 = {{1, 1, 1, 1, 1}, {0, 2, 0, 3, 1}, {0, 0, 2, 2, 1}}
o3 : List
i4 : I = toricIdeal A
2

3 2

4

o4 = ideal (b*c - e , a d- b*e )

o4 : Ideal of Rµ´
変数 a,b,c,d,e がそれぞれ点 1,2,3,4,5 に対応している. 環 R は関数 toricIdeal の中で自動的に定義される.
次のコード triangulate.m21 は M.Stillman, B.Sturmfels, R.Thomas ?? による点集合で定義される aﬃne toric 多様体を計算するプログラムである.
¶

Et/m2-toric.txt³-- M2 book page 181.
toBinomial = (b,R) -> (top := 1_R; bottom := 1_R;
scan(#b, i -> if b_i > 0 then top = top * R_i^(b_i)
else if b_i < 0 then bottom = bottom * R_i^(-b_i));
top - bottom);toricIdeal = (A) -> (n := #(A_0);
R = QQ[vars(0..n-1), Degrees=>transpose A, MonomialSize=>16];
B := transpose LLL syz matrix A;
J := ideal apply(entries B, b-> toBinomial(b,R));scan(gens ring J, f -> J = saturate(J,f));J );µ
このコードの解説はまだ書いてない.
1.

R_i は ring R の i 番目の変数.

2.

b_i は ベクトル b の i 番目成分.

1 なお Macaulay 0.9.95 とそれ以前はパッケージの構成方法が大きく変わっている.
0.9.95 以降では上の入力でload(¨"LLL.m2¨"); は必要ない. ちなみに LLL パッケージを利用場合は loadPackage(¨"LLLBases¨"); コマンドで読み込む.

´

5.5. Toric variety

127

¶

³

i6 : R2=QQ[a,b,c,d,e,Weights=>{{1,1,1,1,0}}]o6 = R2
o6 : PolynomialRing
i10 : F=map(R2,R)
o10 = map(R2,R,{a, b, c, d, e})o10 : RingMap R2 <--- R-- I2 は新しい順序の入った ring でのイデアル.

i11 : I2 = F(I)
2

3 2

4

o11 = ideal (b*c - e , a d- b*e )

o11 : Ideal of R2-- M に I2 の initial ideal を.

i17 : M=monomialIdeal I2
3 2
o17 = monomialIdeal (b*c, a d )o17 : MonomialIdeal of R2

i19 : MM=radical M-- MM は M の radical

o19 = monomialIdeal (b*c, a*d)o19 : MonomialIdeal of R2
i20 : primaryDecomposition MM--MM を準素イデアル分解して三角形分割を得る.

o20 = {monomialIdeal (a, b), monomialIdeal (a, c), monomialIdeal (b, d),monomialIdeal (c, d)}o20 : Listµ
さて, (a, b) の補集合は (c, d, e), 頂点のインデックスでは (3, 4, 5),
さて, (a, c) の補集合は (b, d, e), 頂点のインデックスでは (2, 4, 5),
さて, (b, d) の補集合は (a, c, e), 頂点のインデックスでは (1, 3, 5),
さて, (c, d) の補集合は (a, b, e), 頂点のインデックスでは (1, 2, 5) である. 頂点のインデックスが図

5.5.2 の三角形の頂点と見事に対応していることが観察できるだろう.

´

第5章

128

グレブナ扇と Tropical Geometry

問題 5.1 Voronoi 図は 各点 (x,y) の重みを x2 + y 2 とした正則三角形分割の Dual である. Knop-pix/math icms2006 DVD2 収録の DEpthLaunay による Voronoi 図を M2 による代数計算で構成してみよう.
数学関連事項はテキスト以外に板書でも説明. ビデオ: 2007-05-01 の学生向け解説.

5.5.3

グレブナ基底関連システムのコマンド対応表

Knoppix/Math にはグレブナ基底や可換環論のためのシステムが数通りはいっている. これらの間のコマンドを比較してみよう.

5.5.4

環の定義

たとえば Q[x, y, z] を x の重みが 10, y の重みが 5, z の重みが 0 で順序づけたモノミアル順序の環.

Macaulay2 では¶³

QQ[x,y,z,Weights==>{{10,5,0}}]µ´Singular では
Risa/Asir では¶³[1153] Opt=[["v",[x,y,z]], ["order",[[x,10,y,5]]]];[[v,[x,y,z]], [order,[[x,10,y,5]]]];[1154]µ

dp_gr_main([x^2+y^2+z^2-1,x*y*z-1,x*y+y*z+z*x-3] | option_list=Opt);´とグレブナ基底計算等をおこなうと自動的に現在の環が設定され, 分散表現多項式がこの環に属することとなる.

Kan/sm1 では¶³[(x,y,z) ring_of_polynomials [[(x) 10 (y) 5 (z) 0]] weight_vector 0]
define_ringµ´

normal form の計算
Macaulay2 では % , Risa/Asir では true nf , Kan/sm1 では reduction , Singular では ...
まだ詳しく書いてない

Toric 専用の Gröbner fan の計算システム
asir-contrib の tigers を見よ.

5.5. Toric variety

5.5.5

129

4ti2

4ti2 は toric ideal 専用のグレブナ基底計算プログラムである. (localization と saturation を上手に用いて高速化をはかってるようだ???)
例 5.13
入力プログラム Et/2x2.txt
¶

³

3 4
1 1 0 01 0 1 00 1 0 1row column

3

4

µ

´

実行

groebner 2x2.txt
すると, 2x2.txt.gro というファイル が自動生成される. Et/2x2.txt.gro
¶
1 4
-1 1

1 -1

µ
これの見方の説明.
-1 1 1 -1 は x11 x14 − x12 x13 に対応.
Todo: Et/4ti2 E(2,5) の例.

³
´

第5章

130

5.6

Feasible set の上の乱歩

5.6.1

Toric variety のグレブナ基底の応用

グレブナ扇と Tropical Geometry

数学関連事項はテキスト以外に板書でも説明. ビデオ: 2007-5-1 にした random sampling の学生への説明

5.6.2

Codon の代数的統計学

Todo: この章は当分完成しないかも. 無視してね...
命題 5.1 w(i → k) を状態 i から状態 k への遷移確率とする. 次の条件
(
)
(
)
Ei
Ek
w(i → k) exp −= w(k → i) exp −
kB T
kB T

(5.2)

が成立していれば, この遷移確率で変化していく系は正準分布に近づいていく.
証明. このような系が多数あるとし, いま状態 i にある系が Ni 個であるとする. この多数の系が次の状態に同時に遷移する. この時 状態 i から k へ遷移するものの個数は w(i → k)Ni であり, 状
態 k から i へ遷移するものの個数は w(k → i)Nk である. この和の差は()
w(i → k) Nk
w(i → k)Ni − w(k → i)Nk = Ni w(k → i)−w(k → i)
Ni
)
(


Ek
exp − kB T
N
k

)−
(
= Ni w(k → i) Niiexp − kEBTとなる. Nk /Ni の比が想定値より小さいなら上の式の右辺は正となる. このとき左辺をみれば i からk へ遷移するものの方が, k から i へ遷移するものより多い. よって Nk /Ni の比は増える. Nk /Niの比が想定値より大きい場合も同様である.
右辺が 0 に収束していくことになるが, この時 Nk /Ni の比は正準分布の比に等しい.
条件 (5.2) により一意的に w(i → k) がきまるわけではない. これの決め方には任意性がある.

Metropolis 法では Ek − Ei ≤ 0 の時 1, Ek − Ei > 0 の時()
Ek − Ei
exp −kB Tと選ぶ. この条件は (5.2) を満たす.
この方法を応用して一次元の超幾何多項式の近似計算を試みよう. 我々が考える超幾何多項式は次の和である.

Φ(x) =∑
Ak=β,ki ≥0

1 k
x ,
k!

k! = k1 ! · · · kn !

(5.3)

ここで A は 行列 A = (1, 2), n = 2 である. たとえば β = 6 だとΦ=

x0 y 3x2 y 2x4 y 1x6 y 0
+
+
+
0!3!
2!2!
4!1!
6!0!

となる. β の値を大きくするとこれは巨大な多項式となっていく. ここで Φ(x)/Φ(1) の値を x = 1の近傍で近似計算する問題を考えよう. 考え方としては, Φ(x) に出現する各項を Metropolise 法で

5.6. Feasible set の上の乱歩

131

超幾何分布に従い, 生成する. すべての場合を生成するわけではない. したがって部分和にほかならない. 生成された指数の集合を E と書こう. 我々が計算するのは ΦE (x)/ΦE (1) である. ここで∑

ΦE (x) =k∈E,Ak=β,ki ≥0

xk
k!

(5.4)

である. このような方法でどの程度の近似が計算できるのかは計算実験が必要である. まだやってない
同様に重み付の和∑Φ(ck ; x) =Ak=β,ki ≥0

ck xk
k!

(5.5)

を考えて, Φ(ck ; x)/Φ(x) の値を近似計算する問題も同様の手法で近似計算できると予想できる. 分
母が正確に計算できて, 大きい数だとすると, ΦE (ck ; x)/Φ(x) の近似度はかなりよいはず. まだやってないプログラム 5.1 頻度をグラフ表示する関数. metro1.rr:histgram. metro1.rr:test histプログラム 5.2 逆関数法で正規分布を生成する関数. metro1.rr:g1 metro1.rr:test g1
何故中心部の分布が少ないのか?
プログラム 5.3 metropolis 法で正規分布を生成する関数. metro1.rr:g2t metro1.rr:test g2t
とりあえず正規分布みたいな形を得た. やはり真ん中が引っ込んでるが.
∫ −2
∫ +∞
2
2
Metropolis 法で正規分布を作ろう. このとき −2 以下のものの個数 は −∞ e−x dx/ −∞ e−x dx
生成した乱数の個数に近づくと予想できる. まだためしていない
注意: mpi(); をみればわかるように, 積分値の計算に Metropolise 法は使えない.
√
ところで分母の積分値は π だが, この値を計算できるシステムはあるか?

Integrate[Exp[-x^2],{x,-Infty,Infty}]
Todo: tobe continued.

133

関連図書
[1] David Eisenbud, Daniel R.Grayson, Michael Stillman, Bernd Sturmfels 編, Computations in
Algebraic Geometry with Macaulay 2, Springer, 2002.
[2] Günter M.Ziegler, Lectures on Polytopes (Graduate Texts in Mathematics 152, Springer-Verlag
New York 1995)[3] Komei Fukuda cdd Home Page (http://www.ifor.math.ethz.ch/˜fukuda/cdd home/cdd.html)[4] H.Edelsbrunner, Algorithms in Combinatorial Geometry (Springer-Verlag 1986)[5] David
Speyer,Bernd
Sturmfels,
The
Tropical
http://arxiv.org/abs/math/0304218 (arXiv:math/0304218v3)

Grassmannian,[6] B.Sturmfels, Gröbner basis and convex polytope, 1995
[7] K.Fukuda, A.Jensen, R.Thomas, Computing Gröbner fans, math.AC/0509544[8] T.Bogart, A.Jensen, D.Bayer, B.Sturmfels, R.Thomas, Computing tropical varieties,
math.AC/0507563
このふたつの論文は tropical の計算方法を知るには大事.
[9] J.Richter-Gebert,

B.Sturmfels,

T.Theobald,

First

steps

in

tropicalgeometry,

math.AG/0306366
これは最初に読むおすすめの tropical 幾何入門.
[10] Grigory Mikhalkin, Tropical geometry and its applications, math.AG/0601041
筆者があまりしらない Amoeba よりの解説.
[11] Walker, Algebraic curves, 1950.
代数方程式をべき級数で解く方法の解説がある. Tropical 幾何の基本定理の証明に必要.

[12] B.Sturmfels, Gröbner bases of toric varieties, Tohoku Mathematical Journal, 43, (1991), 249–
261.
Aﬃne toric ideal の Gröbner basis と 三角形分割, Gröbner fan の関連を論じた論文.
2007/knx/st.pdf (パスワード保護) にあり. 同じ著者の本 Gröbner basis and convex polytopeの最初の方も (ideal は homogeneous と仮定して読んでおくと), tropical 幾何と Gröbner fanの関連論文を読むには必読.

[13] Rouchdi Bahloul and Nobuki Takayama, Local Grobner fan: polyhedral and computational
approach, 2005, math.AG/0412044
D-modules, local Gröbner fans, ...