← 戻る ライブラリ › 幾何学 › 高等幾何学 幾何学
熱帯幾何学 通常の加法と乗法を熱帯演算 ⊕ = min \oplus=\min ⊕ = min と ⊗ = + \otimes=+ ⊗ = + に置き換えると、多項式曲線は区分線形なグラフへと姿を変える。その起源は最短経路アルゴリズムにさかのぼり、その先には数え上げ幾何学や非アルキメデス幾何学の未解決問題が広がっている。
直観 普通の算術から熱帯算術へ 「足し算」を2つの価格のうち安いほうを選ぶこと 、「掛け算」をある経路に沿って費用を合計すること だと考えてみよう。+ ∞ +\infty + ∞ を加えた数の集合上に2つの新しい演算を定義する:熱帯加法 a ⊕ b = min ( a , b ) a \oplus b = \min(a, b) a ⊕ b = min ( a , b ) と熱帯乗法 a ⊗ b = a + b a \otimes b = a + b a ⊗ b = a + b である。熱帯多項式 とは、通常の多項式のすべての + + + を ⊕ \oplus ⊕ と読み替え、すべての × \times × を ⊗ \otimes ⊗ と読み替えたものにほかならない。⊗ \otimes ⊗ は単なる足し算なので、x ⊗ 3 x^{\otimes 3} x ⊗ 3 (x x x を熱帯的に3個掛け合わせたもの)のような単項式は 3 x 3x 3 x になり、多項式全体は有限個の一次関数の最小値 へと崩れ落ちる。滑らかな曲線の代わりに、その「零点集合」は、その最小値が少なくとも2つの一次関数の断片で同時に達成される点の集合——つまり角、すなわち区分線形なグラフ ——になる。
なぜ「熱帯(tropical)」と呼ぶのか。この名前は、1970年代後半から理論計算機科学においてmin-plus代数の研究を切り拓いたハンガリー生まれのブラジル人計算機科学者イムレ・シモン (Imre Simon、1943–2009年)に敬意を表したものである。オートマトン理論を専門とするフランス人の同僚たちは、シモンの故郷である南回帰線より南に位置するサンパウロにちなんで、親しみを込めて「熱帯」という形容詞を作った。シュトゥルムフェルスとスパイヤーが後に述べたように、そこに「深い意味は何もない」。min-plus半環の上で代数幾何学を行うと本物の豊かな幾何学的理論が生まれることに数学者たちが気づいたとき、この名前は定着した。
例: 熱帯多項式の値を手計算で求める
1変数の熱帯多項式 p ( x ) = min ( 2 x + 3 , x + 1 , 2 ) p(x) = \min(2x + 3,\ x + 1,\ 2) p ( x ) = min ( 2 x + 3 , x + 1 , 2 ) を考える。これは通常の多項式 2 ⊗ x ⊗ 2 ⊕ 1 ⊗ x ⊕ 2 2 \otimes x^{\otimes 2} \oplus 1 \otimes x \oplus 2 2 ⊗ x ⊗ 2 ⊕ 1 ⊗ x ⊕ 2 (x 2 , x , x 0 x^2, x, x^0 x 2 , x , x 0 に対する係数がそれぞれ 2 , 1 , 2 2, 1, 2 2 , 1 , 2 )に由来する。p ( 1 ) p(1) p ( 1 ) を求めよ。
解答 3つの一次式のそれぞれに x = 1 x = 1 x = 1 を代入する:2 ( 1 ) + 3 = 5 2(1) + 3 = 5 2 ( 1 ) + 3 = 5 、1 + 1 = 2 1 + 1 = 2 1 + 1 = 2 、そして定数項 2 2 2 。熱帯的な値は、これら3つの数の通常の最小値である:p ( 1 ) = min ( 5 , 2 , 2 ) = 2 p(1) = \min(5, 2, 2) = 2 p ( 1 ) = min ( 5 , 2 , 2 ) = 2 。2番目と3番目の式が一致する こと(2 = 2 2 = 2 2 = 2 )に注目してほしい——これはまさに区分線形グラフの角の点 であり、根の熱帯類似物である。
大学 熱帯半環と熱帯曲線 定義: 熱帯半環
熱帯半環 (min-plus 規約による)とは、集合 T = R ∪ { + ∞ } \mathbb{T} = \mathbb{R} \cup \{+\infty\} T = R ∪ { + ∞ } に、熱帯加法 a ⊕ b = min ( a , b ) a \oplus b = \min(a, b) a ⊕ b = min ( a , b ) と熱帯乗法 a ⊗ b = a + b a \otimes b = a + b a ⊗ b = a + b を備えたものである。これは環ではなく半環 である:⊕ \oplus ⊕ と ⊗ \otimes ⊗ は可換かつ結合的で、⊗ \otimes ⊗ は ⊕ \oplus ⊕ に対して分配的だが、+ ∞ +\infty + ∞ 以外のどの元も加法逆元を持たない(有限な a a a に対して min ( a , x ) = + ∞ \min(a, x) = +\infty min ( a , x ) = + ∞ となる数 x x x は存在しない)。加法単位元は + ∞ +\infty + ∞ (min ( a , + ∞ ) = a \min(a, +\infty) = a min ( a , + ∞ ) = a より)、乗法単位元は 0 0 0 (a + 0 = a a + 0 = a a + 0 = a より)である。(双対的な max-plus 規約(⊕ = max \oplus = \max ⊕ = max )も文献では同程度によく使われ、両者は x ↦ − x x \mapsto -x x ↦ − x で対応する。本ページでは一貫して min-plus 規約を用いる。)
n n n 変数の熱帯多項式 とは、有限個の ⊗ \otimes ⊗ -単項式の ⊕ \oplus ⊕ -和、すなわち関数 p : R n → R p : \mathbb{R}^n \to \mathbb{R} p : R n → R で p ( x ) = ⨁ α ∈ S c α ⊗ 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) p ( x ) = ⨁ α ∈ S c α ⊗ x ⊗ α = min α ∈ S ( c α + α ⋅ x ) の形をしたものである。ここで S S S は指数ベクトル α ∈ Z n \alpha \in \mathbb{Z}^n α ∈ Z n からなる有限集合、c α ∈ R c_\alpha \in \mathbb{R} c α ∈ R である。このような p p p はすべて、整数傾きを持つ有限個のアフィン一次関数の各点ごとの最小値であり、したがって区分線形かつ凹 である。p p p が定める熱帯超曲面 (n = 2 n = 2 n = 2 の場合は熱帯曲線 )とは、その角の軌跡 V ( p ) = { x ∈ R n : 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}\} V ( p ) = { x ∈ R n : the minimum in p ( x ) is attained by at least two terms } のことであり——これはまさに p p p が線形でなくなる点の集合、すなわち「多項式が消える場所」の熱帯類似物である。
p ( x ) = ⨁ α ∈ S c α ⊗ 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) p ( x ) = α ∈ S ⨁ c α ⊗ x ⊗ α = α ∈ S min ( c α + α ⋅ x ) n n n 変数の熱帯多項式 とは、有限個の ⊗ \otimes ⊗ -単項式の ⊕ \oplus ⊕ -和、すなわち関数 p : R n → R p : \mathbb{R}^n \to \mathbb{R} p : R n → R で p ( x ) = ⨁ α ∈ S c α ⊗ 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) p ( x ) = ⨁ α ∈ S c α ⊗ x ⊗ α = min α ∈ S ( c α + α ⋅ x ) の形をしたものである。ここで S S S は指数ベクトル α ∈ Z n \alpha \in \mathbb{Z}^n α ∈ Z n からなる有限集合、c α ∈ R c_\alpha \in \mathbb{R} c α ∈ R である。このような p p p はすべて、整数傾きを持つ有限個のアフィン一次関数の各点ごとの最小値であり、したがって区分線形かつ凹 である。p p p が定める熱帯超曲面 (n = 2 n = 2 n = 2 の場合は熱帯曲線 )とは、その角の軌跡 、すなわち少なくとも2つの一次式の断片が最小値で並ぶ点の集合 V ( p ) = { x ∈ R n : ∣ { α ∈ 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\} V ( p ) = { x ∈ R n : ∣ { α ∈ S : c α + α ⋅ x = p ( x )} ∣ ≥ 2 } のことであり——これはまさに p p p が線形でなくなる点の集合、すなわち「多項式が消える場所」の熱帯類似物である。
例: 熱帯直線
2変数で係数がすべて 0 0 0 である、最も単純な次数 1 1 1 の熱帯多項式 q ( x , y ) = x ⊕ y ⊕ 0 = min ( x , y , 0 ) q(x, y) = x \oplus y \oplus 0 = \min(x, y, 0) q ( x , y ) = x ⊕ y ⊕ 0 = min ( x , y , 0 ) を考える。その角の軌跡(それが定める熱帯曲線)を求め、各項が最小値を与える3つの領域を記述せよ。
解答 3つの一次式は x x x 、y y y 、0 0 0 である。これらをペアごとに比較すると:x < y x < y x < y かつ x < 0 x < 0 x < 0 のとき x x x が唯一の最小値となり、y < x y < x y < x かつ y < 0 y < 0 y < 0 のとき y y y が唯一の最小値となり、x > 0 x > 0 x > 0 かつ y > 0 y > 0 y > 0 のとき 0 0 0 が唯一の最小値となる。角の軌跡——2つの式が一致する場所——は、ちょうど原点から出る3本の半直線 からなる:半直線 { x = y ≤ 0 } \{x = y \le 0\} { x = y ≤ 0 } (方向 ( − 1 , − 1 ) (-1,-1) ( − 1 , − 1 ) 、x x x と y y y の式が一致する)、半直線 { x = 0 , y ≥ 0 } \{x = 0,\ y \ge 0\} { x = 0 , y ≥ 0 } (方向 ( 0 , 1 ) (0,1) ( 0 , 1 ) 、x x x の式が定数項と一致する)、半直線 { y = 0 , x ≥ 0 } \{y = 0,\ x \ge 0\} { y = 0 , x ≥ 0 } (方向 ( 1 , 0 ) (1,0) ( 1 , 0 ) 、y y y の式が定数項と一致する)。この三又の図形——「メルセデス・ベンツ」曲線と呼ばれることもある——が熱帯直線であり、通常の直線の熱帯類似物である。
∑ j = 1 k w j v j = 0 \sum_{j=1}^{k} w_j v_j = 0 j = 1 ∑ k w j v j = 0 p p p を2変数の熱帯多項式とし、v v v をその熱帯曲線 V ( p ) V(p) V ( p ) の頂点とする。v v v に接続する V ( p ) V(p) V ( p ) の辺が、原始整数方向ベクトル v 1 , … , v k ∈ Z 2 v_1, \dots, v_k \in \mathbb{Z}^2 v 1 , … , v k ∈ Z 2 (いずれも v v v から離れる向き)と正の整数の重み w 1 , … , w k w_1, \dots, w_k w 1 , … , w k を持つとする。このとき ∑ j = 1 k w j v j = 0 \sum_{j=1}^{k} w_j v_j = 0 ∑ j = 1 k w j v j = 0 が成り立つ。
なぜ正しいのか? これは保存則 であり、構造的には電気回路の節点におけるキルヒホッフの電流則と同一である:v v v の近くでは、多項式 p p p は v v v で等しくなるアフィン片の最小値であり、各辺はそのうちちょうど2つが一致し続ける場所である。v v v の周りを一周歩くと、辺を横切るたびに p p p の傾きは w j v j w_j v_j w j v j に比例する量だけ跳ぶ。p p p は一意に定まる連続関数であるから、これらの跳びは一周した後には打ち消し合わなければならず、それがまさにつり合いの方程式である。単なる多面体複体ではなく、この局所的な打ち消し合いこそが、熱帯曲線を真に代数的 なもの——すなわち、任意の半直線と線分の寄せ集めではなく、正真正銘の熱帯多項式の角の軌跡——たらしめているのである。
証明 p ( x ) = min α ∈ S ( c α + α ⋅ x ) p(x) = \min_{\alpha \in S}(c_\alpha + \alpha \cdot x) p ( x ) = min α ∈ S ( c α + α ⋅ x ) は、各点 α ∈ S \alpha \in S α ∈ S を高さ c α c_\alpha c α に持ち上げてから下側凸包を平面へ射影して得られる、そのニュートン多角形 c o n v ( S ) \mathrm{conv}(S) conv ( S ) の正則細分 Δ p \Delta_p Δ p と双対であることを思い出そう。V ( p ) V(p) V ( p ) の各辺 e e e は Δ p \Delta_p Δ p のある辺 e ∗ e^* e ∗ と双対である:e e e は e ∗ e^* e ∗ と直交し(90 ∘ 90^\circ 9 0 ∘ 回転)、その重み w w w は e ∗ e^* e ∗ の格子長に等しい。V ( p ) V(p) V ( p ) の各頂点 v v v は Δ p \Delta_p Δ p のある 2 2 2 次元胞(多角形)σ v \sigma_v σ v と双対であり、v v v に接続する V ( p ) V(p) V ( p ) の辺は、対応する巡回順序で、ちょうど σ v \sigma_v σ v の境界辺に対応する。閉多角形 σ v \sigma_v σ v の境界を一周たどると、その辺ベクトル e 1 ∗ , … , e k ∗ e_1^*, \dots, e_k^* e 1 ∗ , … , e k ∗ の和はゼロになる——多角形は出発点に戻ってくるからである:e 1 ∗ + ⋯ + e k ∗ = 0 e_1^* + \cdots + e_k^* = 0 e 1 ∗ + ⋯ + e k ∗ = 0 。90 ∘ 90^\circ 9 0 ∘ 回転は線形写像 R R R であり、各 R ( e j ∗ ) R(e_j^*) R ( e j ∗ ) は(固定された向きの選び方のもとで)w j v j w_j v_j w j v j に等しい(重み w j w_j w j は e j ∗ e_j^* e j ∗ の格子長であり、v j v_j v j は e j ∗ e_j^* e j ∗ を回転・原始ベクトルへ再スケールしたものである)。線形写像 R R R を e 1 ∗ + ⋯ + e k ∗ = 0 e_1^* + \cdots + e_k^* = 0 e 1 ∗ + ⋯ + e k ∗ = 0 の両辺に適用すると w 1 v 1 + ⋯ + w k v k = R ( 0 ) = 0 w_1 v_1 + \cdots + w_k v_k = R(0) = 0 w 1 v 1 + ⋯ + w k v k = R ( 0 ) = 0 が得られ、これがまさにつり合い条件である。
上の熱帯直線でつり合い条件を確認してみよう:原点において、3本の半直線の原始方向はそれぞれ ( 1 , 0 ) (1,0) ( 1 , 0 ) 、( 0 , 1 ) (0,1) ( 0 , 1 ) 、( − 1 , − 1 ) (-1,-1) ( − 1 , − 1 ) であり、重みはすべて 1 1 1 である(q q q の係数はすべて 0 0 0 なので、ニュートン三角形の各双対辺の格子長はすべて 1 1 1 である)。実際 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) 1 ⋅ ( 1 , 0 ) + 1 ⋅ ( 0 , 1 ) + 1 ⋅ ( − 1 , − 1 ) = ( 0 , 0 ) となり、この最も単純な例で定理が確かめられる。
発展 形式的付値から真に代数的な理論へ 上の熱帯直線は任意の係数から手で作ったものだが、最も奥深い熱帯曲線は実際の代数多様体を熱帯化(トロピカル化) することから生まれる。K K K を、付値 v a l : K ∗ → R \mathrm{val} : K^* \to \mathbb{R} val : K ∗ → R ——v a l ( a b ) = v a l ( a ) + v a l ( b ) \mathrm{val}(ab) = \mathrm{val}(a) + \mathrm{val}(b) val ( ab ) = val ( a ) + val ( b ) および v a l ( a + b ) ≥ min ( v a l ( a ) , v a l ( b ) ) \mathrm{val}(a+b) \ge \min(\mathrm{val}(a), \mathrm{val}(b)) val ( a + b ) ≥ min ( val ( a ) , val ( b )) を満たす関数——を備えた体とする。例えば、ピュイズー級数体 C { { t } } \mathbb{C}\{\!\{t\}\} C { { t }} (v a l \mathrm{val} val は t t t の最低次の指数を読み取る)や p p p 進数体 Q p \mathbb{Q}_p Q p (v a l \mathrm{val} val は p p p 進付値)である。v a l \mathrm{val} val を座標ごとに拡張して写像 t r o p : ( K ∗ ) n → R n \mathrm{trop} : (K^*)^n \to \mathbb{R}^n trop : ( K ∗ ) n → R n 、t r o p ( x 1 , … , x n ) = ( v a l ( x 1 ) , … , v a l ( x n ) ) \mathrm{trop}(x_1, \dots, x_n) = (\mathrm{val}(x_1), \dots, \mathrm{val}(x_n)) trop ( x 1 , … , x n ) = ( val ( x 1 ) , … , val ( x n )) を得る。多様体 X ⊆ ( K ∗ ) n X \subseteq (K^*)^n X ⊆ ( K ∗ ) n に対し、熱帯化 t r o p ( X ) \mathrm{trop}(X) trop ( X ) とは、像 t r o p ( X ( K ) ) \mathrm{trop}(X(K)) trop ( X ( K )) の R n \mathbb{R}^n R n における閉包のことである。
この形式的な機構を本物の代数幾何学へと結びつける最も重要な事実が、熱帯幾何学の基本定理 である:非自明な付値を持つ代数閉体 K K K 上でイデアル I I I によって切り出される多様体 X = V ( I ) ⊆ ( K ∗ ) n X = V(I) \subseteq (K^*)^n X = V ( I ) ⊆ ( K ∗ ) n に対し、t r o p ( X ) \mathrm{trop}(X) trop ( X ) は、I I I に属するすべての多項式を熱帯化しそれらの角の軌跡の共通部分をとって得られる集合 V ( t r o p ( I ) ) ) V(\mathrm{trop}(I))) V ( trop ( I ))) と一致する——つまり(X X X の実際の点から構成される)解析的 な熱帯化と、イデアルのみから構成される純粋に組合せ論的 な熱帯多様体が一致するのである。超曲面の場合(定義多項式が1つの場合)は1990年代にミハイル・カプラノフによって証明された。任意のイデアルに対する一般的な主張は、グレブナー理論と始めイデアルによる完全な証明とともに、2000年代に開発された熱帯グレブナー基底の手法をもとに、ダイアン・マクラガンとベルント・シュトゥルムフェルスによる 2015 2015 2015 年の教科書『Introduction to Tropical Geometry』において基本定理として展開されている。
誰かがこれを「熱帯」と呼ぶよりずっと前から、計算機科学者たちはすでに手で熱帯線形代数を行っていた。重み付き有向グラフ上の全点対最短経路問題 は ( min , + ) (\min, +) ( min , + ) 代数の教科書的な例である:A A A を、i i i から j j j への辺の重みを A i j A_{ij} A ij とする n × n n \times n n × n 行列とし(辺が存在しないときは A i j = + ∞ A_{ij} = +\infty A ij = + ∞ 、A i i = 0 A_{ii} = 0 A ii = 0 )、熱帯行列積 を通常の線形代数とまったく同じ形で、ただし + + + を ⊕ \oplus ⊕ に、× \times × を ⊗ \otimes ⊗ に置き換えて定義する:( A ⊗ B ) i j = ⨁ k ( A i k ⊗ B k j ) = min k ( A i k + B k j ) (A \otimes B)_{ij} = \bigoplus_k \big(A_{ik} \otimes B_{kj}\big) = \min_k \big(A_{ik} + B_{kj}\big) ( A ⊗ B ) ij = ⨁ k ( A ik ⊗ B k j ) = min k ( A ik + B k j ) 。
d i j ( k ) = min ( d i j ( k − 1 ) , d i k ( k − 1 ) + d k j ( k − 1 ) ) d_{ij}^{(k)} = \min\big(d_{ij}^{(k-1)},\ d_{ik}^{(k-1)} + d_{kj}^{(k-1)}\big) d ij ( k ) = min ( d ij ( k − 1 ) , d ik ( k − 1 ) + d k j ( k − 1 ) ) A A A を、負の重みを持つ閉路がない n n n 頂点の有向グラフの ( min , + ) (\min,+) ( min , + ) 重み行列とする。A ⊗ m A^{\otimes m} A ⊗ m を A A A 自身との m m m 重熱帯行列積とする。このとき成分 ( A ⊗ ( n − 1 ) ) i j (A^{\otimes(n-1)})_{ij} ( A ⊗ ( n − 1 ) ) ij はグラフにおける i i i から j j j への最短経路の長さに等しい。これはまさにFloyd–Warshallアルゴリズム が計算する量であり、その漸化式 d i j ( k ) = min ( d i j ( k − 1 ) , d i k ( k − 1 ) + d k j ( k − 1 ) ) d_{ij}^{(k)} = \min\big(d_{ij}^{(k-1)},\ d_{ik}^{(k-1)} + d_{kj}^{(k-1)}\big) d ij ( k ) = min ( d ij ( k − 1 ) , d ik ( k − 1 ) + d k j ( k − 1 ) ) は A ⊗ ( n − 1 ) A^{\otimes(n-1)} A ⊗ ( n − 1 ) を中間頂点1つずつ順に構築していく。
なぜ正しいのか? 成分 ( A ⊗ m ) i j (A^{\otimes m})_{ij} ( A ⊗ m ) ij は、i i i から j j j への**高々 m m m 本の辺**を使う最良の歩道の長さを追跡する。なぜなら熱帯行列積はまさに「最初の一区間と残りの旅程を足し算で組み合わせ、そのうち最も安い組み合わせだけを残す」ことであり、これは最短経路に対するベルマンの最適性原理そのものだからである。これを n − 1 n - 1 n − 1 回繰り返せば十分である。なぜなら n n n 頂点グラフにおける最短単純経路は n − 1 n - 1 n − 1 本を超える辺を決して必要としないため、それ以上熱帯的に2乗しても答えは改善されないからである。
証明 m m m に関する帰納法で示す。基底段階 m = 1 m = 1 m = 1 :( A ⊗ 1 ) i j = A i j (A^{\otimes 1})_{ij} = A_{ij} ( A ⊗ 1 ) ij = A ij は、高々1本の辺を使う最良の歩道の長さに自明に等しい。帰納段階 :( A ⊗ m ) i k (A^{\otimes m})_{ik} ( A ⊗ m ) ik が、すべての k k k について、高々 m m m 本の辺を使う i i i から k k k への最短歩道の長さに等しいと仮定する。このとき ( A ⊗ ( m + 1 ) ) i j = ( A ⊗ m ⊗ A ) i j = min k ( ( A ⊗ m ) i k + A k j ) (A^{\otimes(m+1)})_{ij} = (A^{\otimes m} \otimes A)_{ij} = \min_k\big((A^{\otimes m})_{ik} + A_{kj}\big) ( A ⊗ ( m + 1 ) ) ij = ( A ⊗ m ⊗ A ) ij = min k ( ( A ⊗ m ) ik + A k j ) となる。i i i から j j j への高々 m + 1 m+1 m + 1 本の辺を使う歩道は、すでに高々 m m m 本の辺しか使っていない(k = j k = j k = j 、A j j = 0 A_{jj} = 0 A j j = 0 の項でカバーされる)か、i i i からある頂点 k k k への高々 m m m 本の辺の歩道に最後の1辺 k → j k \to j k → j を続けたものに分解できる。このようなすべての k k k にわたって最小をとると、ちょうど ( A ⊗ ( m + 1 ) ) i j (A^{\otimes(m+1)})_{ij} ( A ⊗ ( m + 1 ) ) ij が得られるので、主張は m + 1 m + 1 m + 1 でも成り立つ。負の重みの閉路がないため、最短歩道は頂点を繰り返す必要がなく、したがってすべての最短経路は高々 n − 1 n - 1 n − 1 本の辺しか使わない。m = n − 1 m = n - 1 m = n − 1 とすれば ( A ⊗ ( n − 1 ) ) i j (A^{\otimes(n-1)})_{ij} ( A ⊗ ( n − 1 ) ) ij がちょうど最短経路距離であることが示され、これは辺の本数ではなく中間頂点を1つずつ固定して同じ量を計算する Floyd–Warshall の漸化式と一致する。
例: 小さな熱帯行列の2乗
3つの頂点 A , B , C A, B, C A , B , C があり、有向辺は A → B A \to B A → B (重み 4 4 4 )、B → C B \to C B → C (重み 3 3 3 )、A → C A \to C A → C (重み 9 9 9 )である。その ( min , + ) (\min,+) ( min , + ) 重み行列は A = ( 0 4 9 ∞ 0 3 ∞ ∞ 0 ) A = \begin{pmatrix} 0 & 4 & 9 \\ \infty & 0 & 3 \\ \infty & \infty & 0 \end{pmatrix} A = 0 ∞ ∞ 4 0 ∞ 9 3 0 (行・列の順序は A , B , C A, B, C A , B , C )である。( A ⊗ A ) A C (A \otimes A)_{AC} ( A ⊗ A ) A C を計算し、直接の辺の重み 9 9 9 と比較せよ。
解答 定義より ( A ⊗ A ) A C = min k ( A A k + A k C ) = min ( A A A + A A C , A A B + A B C , A A C + A C C ) = 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 ( A ⊗ A ) A C = min k ( A A k + A k C ) = min ( A AA + A A C , A A B + A B C , A A C + A C C ) = min ( 0 + 9 , 4 + 3 , 9 + 0 ) = min ( 9 , 7 , 9 ) = 7 となる。熱帯的な2乗は、合計重み 7 7 7 の2辺経路 A → B → C A \to B \to C A → B → C を見つけ出した。これは重み 9 9 9 の直接辺より確実に安く——B B B を中間頂点として考慮したときに Floyd–Warshall が行う最短経路の更新そのものである。ここでは最短経路がわずか 2 ≤ n − 1 = 2 2 \le n - 1 = 2 2 ≤ n − 1 = 2 本の辺しか使わないため、1回の2乗ですでに十分である。
これはカタログの「s–t フローネットワーク」のグラフを、通常の最大フローとしての役割ではなく、単なる具体的な重み付き有向グラフ として示したものである——これはまさに ( min , + ) (\min,+) ( min , + ) 行列計算が生まれた歴史的な舞台であり、1960年代初頭のFloydとWarshallの最短経路アルゴリズムは、誰もこの代数を「熱帯」と呼ぶ何十年も前に、すでに上で述べた熱帯行列のべき乗をまさに計算していたのである。 熱帯幾何学はまさに交差点に位置している。すべての熱帯多項式 p p p はニュートン多胞体 c o n v ( S ) ⊆ R n \mathrm{conv}(S) \subseteq \mathbb{R}^n conv ( S ) ⊆ R n を伴い、係数 c α c_\alpha c α はその多胞体の正則細分 を誘導する(各 α \alpha α を高さ c α c_\alpha c α に持ち上げ、下側の面を平面へ射影し戻す)——これはまさに凸幾何学・離散幾何学の多面体的な機構である。双対的に、古典的な代数多様体 X X X の熱帯多様体 t r o p ( X ) \mathrm{trop}(X) trop ( X ) は、X X X の本物の代数幾何学的データ(次元、次数、そして交叉理論の多く)を純粋に組合せ論的な対象の中に符号化しており、それゆえ代数幾何学における非常に多くの計算が熱帯的に実行できるのである。そして、すべての熱帯多項式がアフィン一次関数の最小値であるという事実から、その値を計算すること自体が小さな線形計画問題 になる:熱帯幾何学と凸・線形最適化は、同じ基礎となる ( min , + ) (\min, +) ( min , + ) -線形構造を共有しており、熱帯的な手法は今や線形計画法や凸計画法のアルゴリズムに直接取り入れられている。
まず正直に述べておく:これはライブラリの既製3Dポリトープの1つである一般的な四面体 であり、このページの特定の熱帯多項式のニュートン多胞体ではない 。実際のニュートン多胞体(熱帯直線、平面円錐曲線、あるいは上のグラフの例のもの)は通常、R 2 \mathbb{R}^2 R 2 や R 3 \mathbb{R}^3 R 3 内のずっと単純な平らな多角形であり、この形ではない。このウィジェットが正直に示しているのは、平らな面を持ち分解(爆発)できる3D凸ポリトープ という一般的な考え方だけである——これは上で述べた凸幾何学・離散幾何学への橋渡しを支える対象(高さ関数によって細分されるニュートン多胞体)と同種のものである。 発展 百年をかけた形成:オートマトン理論から代数幾何学へ 歴史的ノート
min-plus半環は少なくとも2度、独立に発見された。オペレーションズ・リサーチ の分野では、ロバート・フロイド(1962 1962 1962 年6月、Algorithm 97: Shortest Path )とスティーブン・ワーシャル(1962 1962 1962 年1月、A Theorem on Boolean Matrices )が、バーナード・ロイの1959 1959 1959 年の論文を土台として、現在まとめてFloyd–Warshall と呼ばれる最短経路・推移閉包アルゴリズムを発表した——これらはすべて、振り返れば ( min , + ) (\min,+) ( min , + ) 行列のべき乗の計算であったが、いずれの著者もその言葉は使っていなかった。理論計算機科学 の分野では、イムレ・シモンの1978 1978 1978 年の論文 Limited subsets of a free monoid が、正則言語の有限べき性質を判定するためにmin-plus重み付きオートマトンを導入した。これは後に彼の名を冠することになる半環の直接の先祖である。これら2つの伝統は何十年も並行して進んだ。2000年代 になってようやく、グリゴリー・ミハルキン、ベルント・シュトゥルムフェルス、ダイアン・マクラガン、デイビッド・スパイヤーらの数学者たちが、min-plus半環、ニュートン多胞体、非アルキメデス付値を組み合わせ、現在熱帯幾何学と呼ばれる幾何学的理論を作り上げた——その画期的な成果がミハルキンの *Enumerative tropical algebraic geometry in R 2 \mathbb{R}^2 R 2 *(2005 2005 2005 年)である:この論文は対応定理 を証明し、一般の位置にある点を通る複素代数曲線の古典的な数え上げが、適切に重みづけされた熱帯曲線を数えることで正確に計算できることを示した。これにより、単なる組合せ論的な珍現象にすぎなかったものが、数え上げ代数幾何学の本物の道具へと変貌したのである。
研究 熱帯幾何学の現在地 研究の最前線 2026年時点
2026年時点で 、熱帯幾何学は閉じた一章ではなく、いまなお活発な交差点であり続けている。3つの方向性が際立つ。(1) 数え上げ代数幾何学。 ミハルキンの2005 2005 2005 年の対応定理は数多くの成果の最初の一つにすぎない:熱帯曲線の数え上げ技法は、より高い種数・より高次元の数え上げ問題へと拡張され続けており、古典的手法では直接計算が難しいグロモフ・ウィッテン不変量などの曲線数え上げ理論の計算に活かされている。(2) 計算生物学。 枝の長さを持つ進化系統樹はそれ自体が一種の熱帯的・区分線形な対象であるため、系統樹空間(Billera–Holmes–Vogtmannのツリー空間など)は熱帯線形空間や熱帯グラスマン多様体へ自然に埋め込まれる;これにより研究者は、最尤推定やベイズ的系統推定における扱いにくい組合せ探索の一部を、熱帯凸性や熱帯中央値計算に置き換えることができる。(3) 非アルキメデス幾何学とベルコビッチ幾何学。 熱帯化は現在、非アルキメデス体上の多様体に付随するより豊かな解析的ベルコビッチ空間 の中に座す組合せ論的骨格として理解されている;進行中の研究(ベルコビッチ空間上の微分形式・ポテンシャル論・モンジュ・アンペール方程式、および熱帯的・ベルコビッチ双対複体を通じた曲線モジュライ空間の最高次重みコホモロジーを含む)は、熱帯的組合せ論と非アルキメデス解析幾何学の間の辞書をいっそう精緻にし続けている。未解決問題には、対応定理をより広いクラスの多様体へ拡張することや、どの熱帯多様体が実際に古典的多様体の熱帯化として生じるのかをより深く理解すること(実現可能性 の問題)が含まれる。
このページで使う min-plus 規約において、2 ⊕ 5 2 \oplus 5 2 ⊕ 5 はいくつか。
熱帯多項式 p p p が定める熱帯曲線(角の軌跡)とは、次のような点の集合である。
熱帯化を元に戻して得られる通常の多項式がゼロになる点 p p p を構成する一次式のうち、少なくとも2つが同時に最小値を達成する点p p p が R n \mathbb{R}^n R n 全体で大域的最小値を達成する点その点のすべての座標が 0 0 0 に等しい点 熱帯曲線の頂点におけるつり合い条件 ∑ j w j v j = 0 \sum_j w_j v_j = 0 ∑ j w j v j = 0 が重要である理由は次の通りである。
曲線に直線かつ等しい長さの辺を持つことを強制するから この条件こそが、その複体を任意の多面体複体ではなく真に熱帯多項式の角の軌跡たらしめるものだから 熱帯曲線が有界であることを保証するから それは単なる慣習であり、幾何学的な意味は持たないから
Floyd–Warshall 最短経路アルゴリズムが熱帯幾何学の直接の歴史的祖先である理由は、それが本質的に次を計算しているからである。
グラフの隣接行列の固有値 グラフの重み行列の ( min , + ) (\min, +) ( min , + ) (熱帯)行列べき乗 グラフの重み行列の行列式 ランダムウォークの定常分布