超距離空間
数学において超距離空間(ちょうきょりくうかん、英: ultrametric space)とは、三角不等式が
で置き換えられるような特殊な距離空間のことをいう。対応する距離函数はしばしば非アルキメデス距離や super-metric などとも呼ばれる。超距離空間に対するいくつかの定理は、第一印象では奇妙に感じられるかも知れないが、多くの応用の場面において自然に現れるものである。
定義
厳密に言えば、超距離空間とは点集合 M と以下の性質を満たす函数(距離函数あるいは計量)d との組 (M, d) を言う(紛れの虞の無い場合は、単に台集合 M のみで以て、超距離空間 M などと書く)。R を実数全体の成す集合として、
は、x, y, z ∈ M を任意として
- 正値性:
- 不可識別者同一性(ノルム性):
- 対称性:
- 強三角不等式(超距離不等式):
を満たす。
- 非アルキメデス賦値の場合
- M が 賦値(あるいは 長さ函数(英語版))|•| を持つ 0 付き順序加群 で、その賦値からくる距離 d(すなわち d(x,y) = |x − y|)を考えるときは、超距離不等式はよりきつい評価:
- |x + y| ≤ max{|x|, |y|}, ただし |x| ≠ |y| のときは必ず等号.
- に条件を強めることができる[1][* 1]。|x| = |y| のときは等号が成立してもしなくてもよい。
性質
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1a/Strong_triangle_ineq.svg/220px-Strong_triangle_ineq.svg.png)
上述の定義により、超距離のもつ典型的な性質をいくつか導くことができる。以下、中心 x, 半径 r の(開)球体を
と書く(距離空間の項目を参照)。また、閉球体は右辺の < を ≤ で置き換えたものである。
例えば、超距離空間 M において以下が成り立つ:
x, y, z ∈ M および r, s ∈ R は任意として、
- すべての三角形は鋭二等辺三角形か正三角形である:
- 球体の任意の内点はその球体の中心である:
- 二つの球体が交わるならば、必ず一方が他方に包含される:
- 任意の球体は、距離函数の誘導する位相に関して、開かつ閉集合である。すなわち、開球体は閉でもあり、閉球体は開でもある。
- 半径 r > 0 の与えられた閉球体に中心を持つ半径 r の開球体全体の成す集合は、与えられた閉球体の分割を成す。またこのとき、二つの異なる開球体同士の距離はやはり r に等しい。
これらの内容を証明するのはよい勉強になる[2]。それらはすべて、超距離不等式から導かれる。第二の内容より、球は距離が非ゼロであるようないくつかの中心点を持ちうることに注意されたい。そのような奇妙に思われる結果を直感的に説明する鍵は、強三角不等式により、超距離における距離は足し上げられることがないという事実である。
例
- 離散距離は超距離である。
- p-進数全体の成す集合は完備超距離空間を成す。
- 適当な字母集合 Σ 上の任意の(つまり有限か無限かに関わらない)長さの語からなる集合を考える。二つの異なる語に対し、それらの語が初めて異なる文字となる位置が n であるとき、それらの間の距離を 2−n と定めて得られる距離函数は超距離である。
- 適当な字母集合 Σ 上の、終端が始端と繋がった長さ n の語の集合は、p-close 距離について超距離空間となる。ここで二つの語 x と y が p-close であるとは、p (p < n) 個の連続する文字からなる任意の部分文字列が x と y において同じ回数(0 の場合もある)現れることをいう[3]。
- r = (rn) を上から単調に 0 に収斂する実数列とするとき、|x|r := lim supn→∞ |xn|rn は、それが有限の値となる複素数列 x = (xn) (|x|r < ∞) 全体の成す空間上の超距離を導く(斉次性がないため、|•|r は半ノルムではないことに注意されたい。途中の項 rn が 0 となることも許す場合には、やや稀な規約だが 00 = 0 であるものとする)。
- G が辺重み付き無向グラフであり、すべての辺の重みは正で、d(u,v) は u と v の間のミニマックス経路(英語版)の重み(すなわち、重みを最小化するように経路を選んだときの、ある辺の最大の重み)であるなら、d によって測られる距離に関してそのグラフの頂点は超距離空間を構成する。すべての有限の超距離空間は、この方法で表現されうる[4]。
応用
収縮写像は、計算の最後の結果を近似する方法として知られている(バナッハの不動点定理によってそのような結果の存在は保証される)。同様の考えは、領域理論でも用いられる。p-進解析では、p-進距離が超距離の性質を持つことが重きを以って用いられる(例えば、p-進の解析函数は、複素解析における振る舞いとは異なり、解析接続によって定義域を真に延長することができない)。
応用例は、固体物理学、すなわちジョルジョ・パリージと共同研究者によるレプリカ理論[5]におけるスピングラスの扱いや、非周期的な固体の理論においても見られる[6]。
超距離はまた、UPGMAやWPGMAを使った系統樹の構成や分類学において利用されている[6]。
脚注
注釈
- ^ |x + y| ≤ max{|x|, |y|} (x ≠ y) なるとき、一般性を失うことなく |x| > |y| したがって |x + y| ≤ |x| と仮定してよい。同時に、|x| = |(x + y) − y| ≤ max{|x + y|, |y|} であるが、仮定によりこの右辺が |y| と一致することはない。故に、|x| ≤ |x + y| ≤ |x| したがって |x + y| = |x| が成り立つ。
出典
- ^ Planet Math: ultrametric triangle inequality - PlanetMath.(英語)
- ^ Stack Exchange: Ultrametric Triangle Inequality
- ^ Osipov, Gutkin (2013), “Clustering of periodic orbits in chaotic systems”, Nonlinearity (26): 177–200, doi:10.1088/0951-7715/26/1/177 .
- ^ Leclerc, Bruno (1981), “Description combinatoire des ultramétriques” (French), Centre de Mathématique Sociale. École Pratique des Hautes Études. Mathématiques et Sciences Humaines (73): 5–37, 127, MR623034 .
- ^ Mezard, M; Parisi, G; and Virasoro, M: SPIN GLASS THEORY AND BEYOND, World Scientific, 1986. ISBN 978-9971-5-0116-7
- ^ a b Rammal, R.; Toulouse, G.; Virasoro, M. (1986). “Ultrametricity for physicists”. Reviews of Modern Physics 58 (3): 765–788. doi:10.1103/RevModPhys.58.765. http://rmp.aps.org/abstract/RMP/v58/i3/p765_1 20 June 2011閲覧。.
参考文献
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4a/Commons-logo.svg/30px-Commons-logo.svg.png)
- Kaplansky, I. (1977), Set Theory and Metric Spaces, AMS Chelsea Publishing, ISBN 0-8218-2694-8 .