MathLabs

幾何学

熱帯幾何学

通常の加法と乗法を熱帯演算 ⊕=min⁡\oplus=\min と ⊗=+\otimes=+ に置き換えると、多項式曲線は区分線形なグラフへと姿を変える。その起源は最短経路アルゴリズムにさかのぼり、その先には数え上げ幾何学や非アルキメデス幾何学の未解決問題が広がっている。

直観普通の算術から熱帯算術へ

「足し算」を2つの価格のうち安いほうを選ぶこと、「掛け算」をある経路に沿って費用を合計することだと考えてみよう。+∞+\infty を加えた数の集合上に2つの新しい演算を定義する:熱帯加法 a⊕b=min⁡(a,b)a \oplus b = \min(a, b) と熱帯乗法 a⊗b=a+ba \otimes b = a + b である。熱帯多項式とは、通常の多項式のすべての ++ を ⊕\oplus と読み替え、すべての ×\times を ⊗\otimes と読み替えたものにほかならない。⊗\otimes は単なる足し算なので、x⊗3x^{\otimes 3}(xx を熱帯的に3個掛け合わせたもの)のような単項式は 3x3x になり、多項式全体は有限個の一次関数の最小値へと崩れ落ちる。滑らかな曲線の代わりに、その「零点集合」は、その最小値が少なくとも2つの一次関数の断片で同時に達成される点の集合——つまり角、すなわち区分線形なグラフ——になる。

なぜ「熱帯(tropical)」と呼ぶのか。この名前は、1970年代後半から理論計算機科学においてmin-plus代数の研究を切り拓いたハンガリー生まれのブラジル人計算機科学者イムレ・シモン(Imre Simon、1943–2009年)に敬意を表したものである。オートマトン理論を専門とするフランス人の同僚たちは、シモンの故郷である南回帰線より南に位置するサンパウロにちなんで、親しみを込めて「熱帯」という形容詞を作った。シュトゥルムフェルスとスパイヤーが後に述べたように、そこに「深い意味は何もない」。min-plus半環の上で代数幾何学を行うと本物の豊かな幾何学的理論が生まれることに数学者たちが気づいたとき、この名前は定着した。

例: 熱帯多項式の値を手計算で求める

1変数の熱帯多項式 p(x)=min⁡(2x+3, x+1, 2)p(x) = \min(2x + 3,\ x + 1,\ 2) を考える。これは通常の多項式 2⊗x⊗2⊕1⊗x⊕22 \otimes x^{\otimes 2} \oplus 1 \otimes x \oplus 2(x2,x,x0x^2, x, x^0 に対する係数がそれぞれ 2,1,22, 1, 2)に由来する。p(1)p(1) を求めよ。

解答

3つの一次式のそれぞれに x=1x = 1 を代入する:2(1)+3=52(1) + 3 = 5、1+1=21 + 1 = 2、そして定数項 22。熱帯的な値は、これら3つの数の通常の最小値である:p(1)=min⁡(5,2,2)=2p(1) = \min(5, 2, 2) = 2。2番目と3番目の式が一致すること(2=22 = 2)に注目してほしい——これはまさに区分線形グラフの角の点であり、根の熱帯類似物である。

大学熱帯半環と熱帯曲線

定義: 熱帯半環

熱帯半環(min-plus 規約による)とは、集合 T=R∪{+∞}\mathbb{T} = \mathbb{R} \cup \{+\infty\} に、熱帯加法 a⊕b=min⁡(a,b)a \oplus b = \min(a, b) と熱帯乗法 a⊗b=a+ba \otimes b = a + b を備えたものである。これは環ではなく半環である:⊕\oplus と ⊗\otimes は可換かつ結合的で、⊗\otimes は ⊕\oplus に対して分配的だが、+∞+\infty 以外のどの元も加法逆元を持たない(有限な aa に対して min⁡(a,x)=+∞\min(a, x) = +\infty となる数 xx は存在しない)。加法単位元は +∞+\infty(min⁡(a,+∞)=a\min(a, +\infty) = a より)、乗法単位元は 00(a+0=aa + 0 = a より)である。(双対的な max-plus 規約(⊕=max⁡\oplus = \max)も文献では同程度によく使われ、両者は x↦−xx \mapsto -x で対応する。本ページでは一貫して min-plus 規約を用いる。)

nn 変数の熱帯多項式とは、有限個の ⊗\otimes-単項式の ⊕\oplus-和、すなわち関数 p:Rn→Rp : \mathbb{R}^n \to \mathbb{R} で p(x)=⨁α∈Scα⊗x⊗α=min⁡α∈S(cα+α⋅x)p(x) = \bigoplus_{\alpha \in S} c_\alpha \otimes x^{\otimes \alpha} = \min_{\alpha \in S} \big(c_\alpha + \alpha \cdot x\big) の形をしたものである。ここで SS は指数ベクトル α∈Zn\alpha \in \mathbb{Z}^n からなる有限集合、cα∈Rc_\alpha \in \mathbb{R} である。このような pp はすべて、整数傾きを持つ有限個のアフィン一次関数の各点ごとの最小値であり、したがって区分線形かつ凹である。pp が定める熱帯超曲面(n=2n = 2 の場合は熱帯曲線)とは、その角の軌跡 V(p)={x∈Rn:the minimum in p(x) is attained by at least two terms}V(p) = \{x \in \mathbb{R}^n : \text{the minimum in } p(x) \text{ is attained by at least two terms}\} のことであり——これはまさに pp が線形でなくなる点の集合、すなわち「多項式が消える場所」の熱帯類似物である。

p(x)=⨁α∈Scα⊗x⊗α=min⁡α∈S(cα+α⋅x)p(x) = \bigoplus_{\alpha \in S} c_\alpha \otimes x^{\otimes \alpha} = \min_{\alpha \in S} \big(c_\alpha + \alpha \cdot x\big)

nn 変数の熱帯多項式とは、有限個の ⊗\otimes-単項式の ⊕\oplus-和、すなわち関数 p:Rn→Rp : \mathbb{R}^n \to \mathbb{R} で p(x)=⨁α∈Scα⊗x⊗α=min⁡α∈S(cα+α⋅x)p(x) = \bigoplus_{\alpha \in S} c_\alpha \otimes x^{\otimes \alpha} = \min_{\alpha \in S} \big(c_\alpha + \alpha \cdot x\big) の形をしたものである。ここで SS は指数ベクトル α∈Zn\alpha \in \mathbb{Z}^n からなる有限集合、cα∈Rc_\alpha \in \mathbb{R} である。このような pp はすべて、整数傾きを持つ有限個のアフィン一次関数の各点ごとの最小値であり、したがって区分線形かつ凹である。pp が定める熱帯超曲面(n=2n = 2 の場合は熱帯曲線)とは、その角の軌跡、すなわち少なくとも2つの一次式の断片が最小値で並ぶ点の集合 V(p)={x∈Rn:∣{α∈S:cα+α⋅x=p(x)}∣≥2}V(p) = \{x \in \mathbb{R}^n : |\{\alpha \in S : c_\alpha + \alpha \cdot x = p(x)\}| \ge 2\} のことであり——これはまさに pp が線形でなくなる点の集合、すなわち「多項式が消える場所」の熱帯類似物である。

例: 熱帯直線

2変数で係数がすべて 00 である、最も単純な次数 11 の熱帯多項式 q(x,y)=x⊕y⊕0=min⁡(x,y,0)q(x, y) = x \oplus y \oplus 0 = \min(x, y, 0) を考える。その角の軌跡(それが定める熱帯曲線)を求め、各項が最小値を与える3つの領域を記述せよ。

解答

3つの一次式は xx、yy、00 である。これらをペアごとに比較すると:x<yx < y かつ x<0x < 0 のとき xx が唯一の最小値となり、y<xy < x かつ y<0y < 0 のとき yy が唯一の最小値となり、x>0x > 0 かつ y>0y > 0 のとき 00 が唯一の最小値となる。角の軌跡——2つの式が一致する場所——は、ちょうど原点から出る3本の半直線からなる:半直線 {x=y≤0}\{x = y \le 0\}(方向 (−1,−1)(-1,-1)、xx と yy の式が一致する)、半直線 {x=0, y≥0}\{x = 0,\ y \ge 0\}(方向 (0,1)(0,1)、xx の式が定数項と一致する)、半直線 {y=0, x≥0}\{y = 0,\ x \ge 0\}(方向 (1,0)(1,0)、yy の式が定数項と一致する)。この三又の図形——「メルセデス・ベンツ」曲線と呼ばれることもある——が熱帯直線であり、通常の直線の熱帯類似物である。

∑j=1kwjvj=0\sum_{j=1}^{k} w_j v_j = 0

pp を2変数の熱帯多項式とし、vv をその熱帯曲線 V(p)V(p) の頂点とする。vv に接続する V(p)V(p) の辺が、原始整数方向ベクトル v1,…,vk∈Z2v_1, \dots, v_k \in \mathbb{Z}^2(いずれも vv から離れる向き)と正の整数の重み w1,…,wkw_1, \dots, w_k を持つとする。このとき ∑j=1kwjvj=0\sum_{j=1}^{k} w_j v_j = 0 が成り立つ。

なぜ正しいのか?

これは保存則であり、構造的には電気回路の節点におけるキルヒホッフの電流則と同一である:vv の近くでは、多項式 pp は vv で等しくなるアフィン片の最小値であり、各辺はそのうちちょうど2つが一致し続ける場所である。vv の周りを一周歩くと、辺を横切るたびに pp の傾きは wjvjw_j v_j に比例する量だけ跳ぶ。pp は一意に定まる連続関数であるから、これらの跳びは一周した後には打ち消し合わなければならず、それがまさにつり合いの方程式である。単なる多面体複体ではなく、この局所的な打ち消し合いこそが、熱帯曲線を真に代数的なもの——すなわち、任意の半直線と線分の寄せ集めではなく、正真正銘の熱帯多項式の角の軌跡——たらしめているのである。

証明

p(x)=min⁡α∈S(cα+α⋅x)p(x) = \min_{\alpha \in S}(c_\alpha + \alpha \cdot x) は、各点 α∈S\alpha \in S を高さ cαc_\alpha に持ち上げてから下側凸包を平面へ射影して得られる、そのニュートン多角形 conv(S)\mathrm{conv}(S) の正則細分 Δp\Delta_p と双対であることを思い出そう。V(p)V(p) の各辺 ee は Δp\Delta_p のある辺 e∗e^* と双対である:ee は e∗e^* と直交し(90∘90^\circ 回転)、その重み ww は e∗e^* の格子長に等しい。V(p)V(p) の各頂点 vv は Δp\Delta_p のある 22 次元胞(多角形)σv\sigma_v と双対であり、vv に接続する V(p)V(p) の辺は、対応する巡回順序で、ちょうど σv\sigma_v の境界辺に対応する。閉多角形 σv\sigma_v の境界を一周たどると、その辺ベクトル e1∗,…,ek∗e_1^*, \dots, e_k^* の和はゼロになる——多角形は出発点に戻ってくるからである:e1∗+⋯+ek∗=0e_1^* + \cdots + e_k^* = 0。90∘90^\circ 回転は線形写像 RR であり、各 R(ej∗)R(e_j^*) は(固定された向きの選び方のもとで)wjvjw_j v_j に等しい(重み wjw_j は ej∗e_j^* の格子長であり、vjv_j は ej∗e_j^* を回転・原始ベクトルへ再スケールしたものである)。線形写像 RR を e1∗+⋯+ek∗=0e_1^* + \cdots + e_k^* = 0 の両辺に適用すると w1v1+⋯+wkvk=R(0)=0w_1 v_1 + \cdots + w_k v_k = R(0) = 0 が得られ、これがまさにつり合い条件である。

上の熱帯直線でつり合い条件を確認してみよう:原点において、3本の半直線の原始方向はそれぞれ (1,0)(1,0)、(0,1)(0,1)、(−1,−1)(-1,-1) であり、重みはすべて 11 である(qq の係数はすべて 00 なので、ニュートン三角形の各双対辺の格子長はすべて 11 である)。実際 1⋅(1,0)+1⋅(0,1)+1⋅(−1,−1)=(0,0)1\cdot(1,0) + 1\cdot(0,1) + 1\cdot(-1,-1) = (0,0) となり、この最も単純な例で定理が確かめられる。

発展形式的付値から真に代数的な理論へ

上の熱帯直線は任意の係数から手で作ったものだが、最も奥深い熱帯曲線は実際の代数多様体を熱帯化(トロピカル化)することから生まれる。KK を、付値 val:K∗→R\mathrm{val} : K^* \to \mathbb{R}——val(ab)=val(a)+val(b)\mathrm{val}(ab) = \mathrm{val}(a) + \mathrm{val}(b) および val(a+b)≥min⁡(val(a),val(b))\mathrm{val}(a+b) \ge \min(\mathrm{val}(a), \mathrm{val}(b)) を満たす関数——を備えた体とする。例えば、ピュイズー級数体 C{ ⁣{t}}\mathbb{C}\{\!\{t\}\}(val\mathrm{val} は tt の最低次の指数を読み取る)や pp進数体 Qp\mathbb{Q}_p(val\mathrm{val} は pp進付値)である。val\mathrm{val} を座標ごとに拡張して写像 trop:(K∗)n→Rn\mathrm{trop} : (K^*)^n \to \mathbb{R}^n、trop(x1,…,xn)=(val(x1),…,val(xn))\mathrm{trop}(x_1, \dots, x_n) = (\mathrm{val}(x_1), \dots, \mathrm{val}(x_n)) を得る。多様体 X⊆(K∗)nX \subseteq (K^*)^n に対し、熱帯化 trop(X)\mathrm{trop}(X) とは、像 trop(X(K))\mathrm{trop}(X(K)) の Rn\mathbb{R}^n における閉包のことである。

この形式的な機構を本物の代数幾何学へと結びつける最も重要な事実が、熱帯幾何学の基本定理である:非自明な付値を持つ代数閉体 KK 上でイデアル II によって切り出される多様体 X=V(I)⊆(K∗)nX = V(I) \subseteq (K^*)^n に対し、trop(X)\mathrm{trop}(X) は、II に属するすべての多項式を熱帯化しそれらの角の軌跡の共通部分をとって得られる集合 V(trop(I)))V(\mathrm{trop}(I))) と一致する——つまり(XX の実際の点から構成される)解析的な熱帯化と、イデアルのみから構成される純粋に組合せ論的な熱帯多様体が一致するのである。超曲面の場合(定義多項式が1つの場合)は1990年代にミハイル・カプラノフによって証明された。任意のイデアルに対する一般的な主張は、グレブナー理論と始めイデアルによる完全な証明とともに、2000年代に開発された熱帯グレブナー基底の手法をもとに、ダイアン・マクラガンとベルント・シュトゥルムフェルスによる 20152015 年の教科書『Introduction to Tropical Geometry』において基本定理として展開されている。

誰かがこれを「熱帯」と呼ぶよりずっと前から、計算機科学者たちはすでに手で熱帯線形代数を行っていた。重み付き有向グラフ上の全点対最短経路問題は (min⁡,+)(\min, +) 代数の教科書的な例である:AA を、ii から jj への辺の重みを AijA_{ij} とする n×nn \times n 行列とし(辺が存在しないときは Aij=+∞A_{ij} = +\infty、Aii=0A_{ii} = 0)、熱帯行列積を通常の線形代数とまったく同じ形で、ただし ++ を ⊕\oplus に、×\times を ⊗\otimes に置き換えて定義する:(A⊗B)ij=⨁k(Aik⊗Bkj)=min⁡k(Aik+Bkj)(A \otimes B)_{ij} = \bigoplus_k \big(A_{ik} \otimes B_{kj}\big) = \min_k \big(A_{ik} + B_{kj}\big)。

dij(k)=min⁡(dij(k−1), dik(k−1)+dkj(k−1))d_{ij}^{(k)} = \min\big(d_{ij}^{(k-1)},\ d_{ik}^{(k-1)} + d_{kj}^{(k-1)}\big)

AA を、負の重みを持つ閉路がない nn 頂点の有向グラフの (min⁡,+)(\min,+) 重み行列とする。A⊗mA^{\otimes m} を AA 自身との mm 重熱帯行列積とする。このとき成分 (A⊗(n−1))ij(A^{\otimes(n-1)})_{ij} はグラフにおける ii から jj への最短経路の長さに等しい。これはまさにFloyd–Warshallアルゴリズムが計算する量であり、その漸化式 dij(k)=min⁡(dij(k−1), dik(k−1)+dkj(k−1))d_{ij}^{(k)} = \min\big(d_{ij}^{(k-1)},\ d_{ik}^{(k-1)} + d_{kj}^{(k-1)}\big) は A⊗(n−1)A^{\otimes(n-1)} を中間頂点1つずつ順に構築していく。

なぜ正しいのか?

成分 (A⊗m)ij(A^{\otimes m})_{ij} は、ii から jj への**高々 mm 本の辺**を使う最良の歩道の長さを追跡する。なぜなら熱帯行列積はまさに「最初の一区間と残りの旅程を足し算で組み合わせ、そのうち最も安い組み合わせだけを残す」ことであり、これは最短経路に対するベルマンの最適性原理そのものだからである。これを n−1n - 1 回繰り返せば十分である。なぜなら nn 頂点グラフにおける最短単純経路は n−1n - 1 本を超える辺を決して必要としないため、それ以上熱帯的に2乗しても答えは改善されないからである。

証明

mm に関する帰納法で示す。基底段階 m=1m = 1:(A⊗1)ij=Aij(A^{\otimes 1})_{ij} = A_{ij} は、高々1本の辺を使う最良の歩道の長さに自明に等しい。帰納段階:(A⊗m)ik(A^{\otimes m})_{ik} が、すべての kk について、高々 mm 本の辺を使う ii から kk への最短歩道の長さに等しいと仮定する。このとき (A⊗(m+1))ij=(A⊗m⊗A)ij=min⁡k((A⊗m)ik+Akj)(A^{\otimes(m+1)})_{ij} = (A^{\otimes m} \otimes A)_{ij} = \min_k\big((A^{\otimes m})_{ik} + A_{kj}\big) となる。ii から jj への高々 m+1m+1 本の辺を使う歩道は、すでに高々 mm 本の辺しか使っていない(k=jk = j、Ajj=0A_{jj} = 0 の項でカバーされる)か、ii からある頂点 kk への高々 mm 本の辺の歩道に最後の1辺 k→jk \to j を続けたものに分解できる。このようなすべての kk にわたって最小をとると、ちょうど (A⊗(m+1))ij(A^{\otimes(m+1)})_{ij} が得られるので、主張は m+1m + 1 でも成り立つ。負の重みの閉路がないため、最短歩道は頂点を繰り返す必要がなく、したがってすべての最短経路は高々 n−1n - 1 本の辺しか使わない。m=n−1m = n - 1 とすれば (A⊗(n−1))ij(A^{\otimes(n-1)})_{ij} がちょうど最短経路距離であることが示され、これは辺の本数ではなく中間頂点を1つずつ固定して同じ量を計算する Floyd–Warshall の漸化式と一致する。

例: 小さな熱帯行列の2乗

3つの頂点 A,B,CA, B, C があり、有向辺は A→BA \to B(重み 44)、B→CB \to C(重み 33)、A→CA \to C(重み 99)である。その (min⁡,+)(\min,+) 重み行列は A=(049∞03∞∞0)A = \begin{pmatrix} 0 & 4 & 9 \\ \infty & 0 & 3 \\ \infty & \infty & 0 \end{pmatrix}(行・列の順序は A,B,CA, B, C)である。(A⊗A)AC(A \otimes A)_{AC} を計算し、直接の辺の重み 99 と比較せよ。

解答

定義より (A⊗A)AC=min⁡k(AAk+AkC)=min⁡(AAA+AAC, AAB+ABC, AAC+ACC)=min⁡(0+9, 4+3, 9+0)=min⁡(9,7,9)=7(A \otimes A)_{AC} = \min_k(A_{Ak} + A_{kC}) = \min\big(A_{AA}+A_{AC},\ A_{AB}+A_{BC},\ A_{AC}+A_{CC}\big) = \min(0+9,\ 4+3,\ 9+0) = \min(9, 7, 9) = 7 となる。熱帯的な2乗は、合計重み 77 の2辺経路 A→B→CA \to B \to C を見つけ出した。これは重み 99 の直接辺より確実に安く——BB を中間頂点として考慮したときに Floyd–Warshall が行う最短経路の更新そのものである。ここでは最短経路がわずか 2≤n−1=22 \le n - 1 = 2 本の辺しか使わないため、1回の2乗ですでに十分である。

指定された源点と沈点、およびいくつかの中間頂点が有向辺で結ばれた有向グラフ。ここでは通常の最大フローの用途ではなく、min-plus(最短経路)行列計算を説明するための一般的な重み付きネットワークとして描かれている。
これはカタログの「s–t フローネットワーク」のグラフを、通常の最大フローとしての役割ではなく、単なる具体的な重み付き有向グラフとして示したものである——これはまさに (min⁡,+)(\min,+) 行列計算が生まれた歴史的な舞台であり、1960年代初頭のFloydとWarshallの最短経路アルゴリズムは、誰もこの代数を「熱帯」と呼ぶ何十年も前に、すでに上で述べた熱帯行列のべき乗をまさに計算していたのである。

熱帯幾何学はまさに交差点に位置している。すべての熱帯多項式 pp はニュートン多胞体 conv(S)⊆Rn\mathrm{conv}(S) \subseteq \mathbb{R}^n を伴い、係数 cαc_\alpha はその多胞体の正則細分を誘導する(各 α\alpha を高さ cαc_\alpha に持ち上げ、下側の面を平面へ射影し戻す)——これはまさに凸幾何学・離散幾何学の多面体的な機構である。双対的に、古典的な代数多様体 XX の熱帯多様体 trop(X)\mathrm{trop}(X) は、XX の本物の代数幾何学的データ(次元、次数、そして交叉理論の多く)を純粋に組合せ論的な対象の中に符号化しており、それゆえ代数幾何学における非常に多くの計算が熱帯的に実行できるのである。そして、すべての熱帯多項式がアフィン一次関数の最小値であるという事実から、その値を計算すること自体が小さな線形計画問題になる:熱帯幾何学と凸・線形最適化は、同じ基礎となる (min⁡,+)(\min, +)-線形構造を共有しており、熱帯的な手法は今や線形計画法や凸計画法のアルゴリズムに直接取り入れられている。

回転可能な3D四面体(三角形の面が4枚)で、「爆発」スライダーを使って面を中心から引き離すことができる。特定の多項式のニュートン多胞体ではなく、凸ポリトープの一般的な形の模式的な代用として示されている。
まず正直に述べておく:これはライブラリの既製3Dポリトープの1つである一般的な四面体であり、このページの特定の熱帯多項式のニュートン多胞体ではない。実際のニュートン多胞体(熱帯直線、平面円錐曲線、あるいは上のグラフの例のもの)は通常、R2\mathbb{R}^2 や R3\mathbb{R}^3 内のずっと単純な平らな多角形であり、この形ではない。このウィジェットが正直に示しているのは、平らな面を持ち分解(爆発)できる3D凸ポリトープという一般的な考え方だけである——これは上で述べた凸幾何学・離散幾何学への橋渡しを支える対象(高さ関数によって細分されるニュートン多胞体)と同種のものである。

発展百年をかけた形成:オートマトン理論から代数幾何学へ

研究熱帯幾何学の現在地

このページで使う min-plus 規約において、2⊕52 \oplus 5 はいくつか。

熱帯多項式 pp が定める熱帯曲線(角の軌跡)とは、次のような点の集合である。

熱帯曲線の頂点におけるつり合い条件 ∑jwjvj=0\sum_j w_j v_j = 0 が重要である理由は次の通りである。

Floyd–Warshall 最短経路アルゴリズムが熱帯幾何学の直接の歴史的祖先である理由は、それが本質的に次を計算しているからである。

参考文献

  1. Diane Maclagan, Bernd Sturmfels (2015). Introduction to Tropical Geometry
  2. Grigory Mikhalkin (2005). Enumerative tropical algebraic geometry in R^2 · arXiv:math/0312530
  3. Imre Simon (1978). Limited subsets of a free monoid · DOI:10.1109/SFCS.1978.21