群の自然な準同型と部分群の対応
群Gとその正規部分群Nがあるとする。Gから剰余群G/Nへの自然な準同型をとする。G/Nの部分群全体の集合を、GのNを含む部分群全体の集合をとする。このとき、写像は全単射となる。つまり、との元の間には一対一の対応関係がある。例によって細かい理屈はここでは述べないが、今日はこの事実を具体例を用いて可視化してみようと思う。
ある程度大きい群でないと上記事実のイメージを掴むのに役立たないので、位数12の群で考えてみる。位数12の群の中でも適度に複雑なものとして、二面体群が挙げられる。これは正六角形に対する合同変換全体が成す群である。状況をクリアにするために、ここでは正六角形の中心が二次元ユークリッド空間の原点にあり、さらに2つの互いに反対側に位置する頂点がx軸上に乗っているとする。
は回転と鏡像反転の操作によって生成される。ここでは原点を中心に半時計回りの方向に回転する操作を、x軸に対して反転する操作をと呼ぶことにする。すると、の元は以下のように表すことができる。
次に、正規部分群を1つ選んでみる。ここでは以下の群を使うことにしよう。
このとき、群Nに関するの同値類は以下のように分類できる。
これらがの元になる。すなわち、となる。ここで、単位元はNである。はクラインの四元群となっており、以下の5つの部分群が存在する。
これで剰余群の部分群が分かった。続いて、これらと一対一に対応するの部分群を求めてみる。定理によると、それはNを含む部分群になる。以下に具体的に列挙する。
これで役者は全て出揃った。あとはこれらの対応関係を図示すれば目的は達せられる。しかし、その前にちょっと寄り道をして、ここまでに求めた集合や群の定性的意味を考えてみたいと思う。それが分かれば、最後に可視化を行った際に、状況がよりクリアに理解できるだろう。
まずNの元について考えてみる。これは一体どういう部分群になっているだろうか?ずばり、偶数回の回転操作のみを集めた部分群になっている*1。そこから得られた剰余類はそれぞれ何を表しているのだろうか?実は、は奇数回の回転操作、は反転した状態での偶数回の回転操作、そしては反転した状態での奇数回の回転操作を表している。
ここまでくると、剰余群の元が表しているものが分かってくる。この剰余群は偶数回の回転操作の集まりNで割ることによって得られるので、偶数回の回転操作を全て同一視していることになる。すなわち、0回転だろうが2回転だろうが4回転だろうが、結局どれも偶数回の回転操作なんだから、細かい回転数は無視してまとめて考えてしまおうというのである。そのため、の元は具体的な回転数を無視した、{偶数回転、奇数回転、反転偶数回転、反転奇数回転}という抽象的な操作の集まりから成る群であると考えることができる。
そうした時に、例えばというのは偶数回転と奇数回転を合わせたものになっているし、は偶数回転と反転偶数回転を合わせたものになっている。また、は具体的に偶数回転と奇数回転を表す元を全て寄せ集めたものになっており、は偶数回転と反転偶数回転を表す元の寄せ集めになっているのである。これが上記登場人物たちの定性的解釈である。
では、これらの関係を図示してみよう。
上図左側が、右側がである。また、自明な部分群については記載を省略している。これで随分と関係がはっきりしたのではなかろうか。
本稿の内容は私がぼんやりとしか理解できていなかった部分をはっきりさせるために書いたのだが、このレベルまで考察と可視化を行うと、もはや冒頭に書いた定理は自明にさえ思えてきた。数学というのは分からないうちはさっぱり分からないのに、分かってしまうと本当に当たり前に思えてくるから不思議なものだ。
参考
- 作者: 雪江明彦
- 出版社/メーカー: 日本評論社
- 発売日: 2010/11/17
- メディア: 単行本(ソフトカバー)
- 購入: 1人 クリック: 21回
- この商品を含むブログを見る
有限生成アーベル群の基本定理にまつわる考察
群論の有名な定理の1つに有限生成アーベル群の基本定理というものがある。これは、群Gが有限生成アーベル群であれば、Gは巡回群の直積に分解できるというものである。より具体的には以下の通りである。
群Gが有限生成アーベル群であれば、となるような自然数と非負整数rがあり、となる。
最初にこの定理を学んだときは、「そういう定理もあるのか」という程度で通りすぎてしまったのだが、代数学を一通り学んだ今になって、いくつか疑問が湧いてきた。それらは大別すると以下の2つに分けられる。
- 代数学に登場する類似の定理とはどのように関連しているのか?
- この定理からどんなことが分かるのか?
本稿ではこの2つの疑問に対する答えについて、もがきながら足掻きながら必死に調べ、考え、理解を試みた末に、現段階までに知り得たことを書いてみる。
有限生成アーベル群の基本定理と仲間たち
有限生成アーベル群の基本定理と似たような定理として、私が関連がありそうだと思ったものを以下に挙げる。
上から順に関連について述べていき、最後に関係をまとめてみる。
中国式剰余定理(巡回群に関するもの)
巡回群に関する中国式剰余定理とは以下のような定理である。
m, nを互いに素な自然数とする。このとき、となる。
この定理が述べているのは、あくまで元々の群が巡回群の時に、それを互いに素な自然数に着目して分解できるというものである。一方、有限生成アーベル群の基本定理では、群が巡回群であることは一切仮定していない。にもかかわらず、それが実は巡回群の直積に分解できるというところがミソなのである。
なお、巡回群は有限生成アーベル群となるため、本定理は有限生成アーベル群の基本定理に含まれる。
有限アーベル群の基本定理
この定理には最初とても混乱させられた。まず、この定理の主張は以下のようになる。
群Gが有限アーベル群であれば、となるような自然数があり、となる。
なんだか有限生成アーベル群の基本定理と似ている。違いはの項がないことである。それもそのはずで、有限アーベル群であるということは当然有限生成アーベル群であることを意味するため、本定理は有限生成アーベル群の基本定理に含まれるものである。
単項イデアル整域上の有限生成加群の構造定理
名前だけ見るとなんのことだかさっぱり分からない本定理は、実は有限生成アーベル群の基本定理を一般化したものである。本定理は単項イデアル整域上の有限生成加群に関するものであるが、有限生成アーベル群は加群であり、かつ加群として有限生成である。また、は単項イデアル整域であるため、有限生成アーベル群の基本定理が本定理に含まれることは納得できるだろう。詳細は適当な代数学の本を参照して欲しい。
第一の疑問に対する回答まとめ
以上で私の疑問はだいぶすっきりした。結局、以下のような図式が成り立っていたのだ。(絵心が足りないのは許していただきたい。)
有限生成アーベル群の基本定理から分かること
証明の概略
ここからは第二の疑問について考えてみる。そのために、まず証明の概略について述べる。
群Gが有限生成アーベル群であるとする。Gがm個の元により生成されるとすると、階数m*1の自由アーベル群からGへの全射準同型fが存在する*2。Ker(f)はの部分群となり、かつそれ自身自由アーベル群となる。準同型定理よりとなる。よって、右辺の構造について詳細に調べることにする。
の基底を、Ker(f)の基底をとする。ただし、である。Ker(f)はの部分群なので、Ker(f)の基底は全ての基底の線形結合として書き表すことができる。
ただし、である。これを行列で書き換えると以下のようになる。
P, Qを適当な正則行列とすると、上記の式は以下のように変形できることが知られている。(ここでは証明しない。)
、及びはそれぞれ、及びという基底を行列Q, Pにより変換したものになっており、本質的には同じ空間を表している。そこで、, Ker(f)の基底をそれぞれ、及びに取り直す。であり、また上で得られた式からとなるので、結局以下が得られる。
以上が定理の証明の概略である。
定理の考察
さて、この定理について更に深く考えると、一体どんな世界が見えてくるのだろうか。まず証明の過程に着目してみよう。上で述べた証明の中では、とKer(f)の基底をうまく取り替えることによって、それらの間の変換行列をとてもシンプルな形に変形することができた。ここで、変換後のKer(f)の基底は、同じく変換後のの基底のうち、最初のn個のそれぞれ定数倍となっている。さらに、の基底のうち、n+1個目以降はKer(f)には一切影響を与えていない。このことから、証明の中で行われた基底の変換は、の最初のn個の基底とKer(f)の基底がそれぞれ同じ方向を向くように調整する操作だったのだと考えることができる。このような基底の方向調整は、代数学のみならず他の数学分野にも登場する操作であり、大変興味深い。
次に、定理の最終的な主張の形に着目してみよう。大きな特徴として、この式は位数有限の巡回群と位数無限の巡回群の直積になっていることが分かる。アーベル群のある元gの位数が有限であるということは、すなわちその元をd回足し合わせることで単位元に戻るということである。式で書けばである。このような元のことを捩れ元と呼び、捩れ元全体から成る集合はGの部分群になる。そのような部分群をGの捩れ部分群と呼ぶ。本定理の主張は、有限生成なアーベル群が捩れ部分群とそれ以外とに分けられるということを述べていたのである。
ここで1つ私が抱いた疑問について述べる。それは、自由アーベル群と有限生成アーベル群の本質的な違いは何かということである。というのも、自由アーベル群はその基底の線形結合で全ての元を表現でき、また有限生成アーベル群はその生成元の線形結合でやはり全ての元を表現できるので、ぱっと見ただけだと違いがよく分からないのである。その答えがまさに捩れの有無にあるのだ。つまり、自由アーベル群には捩れがなく、有限生成アーベル群には捩れがあるかもしれないということである。そして、この捩れがどれくらい大きな割合を占めているのかということが、ある有限生成アーベル群が自由アーベル群からどれくらいかけ離れているのかを示していると解釈できるのである。ついでに、このような関係から直感的に自由アーベル群の方が集合として大きく、結果的に有限生成アーベル群への全射準同型が構成できることにも納得ができた。
まとめ
以上、有限生成アーベル群に関して私が調べたこと・考えたことについて書いてみた。本定理の主張は非常にパワフルであるだけでなく、その背景には群論、環論、及び線形代数などに関するさまざまな事実との関連があり、大変興味深いものであった。
本稿の内容をまとめるだけの理解を得るのに、実に1週間以上の日数を要した。数学を理解するというのは本当に大変だ。
参考
http://amano-katsutoshi.com/lec2014/algebraIA-ex/algebraIA-ex20140528.pdf
http://www2.math.cst.nihon-u.ac.jp/sasaki/wp/wp-content/uploads/2014/12/fa75a316529d0ac746d8f50958ba66ed.pdf
- 作者: 雪江明彦
- 出版社/メーカー: 日本評論社
- 発売日: 2010/11/17
- メディア: 単行本(ソフトカバー)
- 購入: 1人 クリック: 21回
- この商品を含むブログを見る
- 作者: 雪江 明彦
- 出版社/メーカー: 日本評論社
- 発売日: 2010/12/07
- メディア: 単行本(ソフトカバー)
- 購入: 2人 クリック: 14回
- この商品を含むブログを見る
有限次分離拡大が単拡大となることの具体例を愚直に計算してみる
体の拡大L/Kが有限次分離拡大であるとき、この拡大は単拡大になることが知られている。私が使っている教科書にもこの定理は載っており、具体例としてが取り上げられていた。しかし、その説明が私にはエレンガント過ぎて、なんともピンとこなかった。私がとにかく疑問だったのは、一体の元の四則演算でどうやってやを生み出せるのか、その具体的な計算手順は何かということだ。タネが分かった今となっては難しくもなんとも無いが、同じ疑問でハマる人がいないとも限らないので、本稿を書いてみることにした。
手順はとても簡単だ。まず、である。これを3乗すると以下のようになる。
これからを引いて2で割るとが得られる。
これでが分かった。すると、即座に
が得られる。結局、となることが分かった。以上で説明はおしまいである。
ポイントはを3乗することである。私は初め2乗を試してうまくいかず、悩みこんでしまった。分かってしまえばなんでこんなことも分からなかったのかと思うくらい簡単だが、こういうのは本当にコロンブスの卵だなぁ。
数式処理システムSageMathで遊ぶ
代数学について勉強していると、具体的な群の構造やら何やらを知りたくなる時がある。しかし、それらを理論的に求めることができたとしても、実際に計算してみるのは大変骨の折れることだ。例えば、ある群の部分群を全て知りたいとか、ある多項式のガロア群を求めたいとか思っても、実際にはなかなか計算することは難しい。
そこで調べてみたところ、世の中にはこのような代数学に関する計算を行うためのソフトウェアが存在していた。その名もSageMath(以下、sage)である。Sageは数学に関する様々な計算を行えるオープンソースソフトウェアであり、interfaceにはpythonベースの言語を使用する。以下に本家へのリンクを貼っておく。
今回は冒頭で述べた群の部分群を全て求めるという計算と、多項式のガロア群を求める計算を実際に行ってみたので、それについて記載する。
初めに注意しておくと、実はビルドの途中でmakeコマンドがうんともすんとも言わなくなり、やむなくCtrl+Cで強制終了した。ただ、どうもコンソール出力の内容から察するに、コケていたのはドキュメントのビルドだと思われるので、sage自体は問題なく使えている。
準備:基本的な群を求める
群の例で遊んでみるにあたり、基本的な群を自分で構築するのは面倒である。素晴らしいことに、sageでは基本的な群はすぐに取得できるように関数が用意されている。例えば3次対称群が欲しければ以下のコマンドを実行すればよい。
sage: S3 = SymmetricGroup(3)
これで3次対称群が変数S3に代入された。これの中を見るには以下のようにすればよい。
sage: S3 Symmetric group of order 3! as a permutation group sage: S3.list() [(), (1,2), (1,2,3), (1,3,2), (2,3), (1,3)]
その他の例として、交代群、二面体群を求めるコマンドも紹介しておく。
sage: A3 = AlternatingGroup(3) # 3次交代群 sage: A3 Alternating group of order 3!/2 as a permutation group sage: A3.list() [(), (1,2,3), (1,3,2)] sage: D4 = DihedralGroup(4) # 4次二面体群 sage: D4 Dihedral group of order 8 as a permutation group sage: D4.list() [(), (1,4)(2,3), (1,2,3,4), (1,3)(2,4), (1,3), (2,4), (1,4,3,2), (1,2)(3,4)]
群の部分群を全て求める
群の部分群を全て求めるには、subgroups関数を使用する。
sage: S3.subgroups() [Subgroup of (Symmetric group of order 3! as a permutation group) generated by [()], Subgroup of (Symmetric group of order 3! as a permutation group) generated by [(2,3)], Subgroup of (Symmetric group of order 3! as a permutation group) generated by [(1,2)], Subgroup of (Symmetric group of order 3! as a permutation group) generated by [(1,3)], Subgroup of (Symmetric group of order 3! as a permutation group) generated by [(1,2,3)], Subgroup of (Symmetric group of order 3! as a permutation group) generated by [(2,3), (1,2,3)]]
ここに表示されていることの意味は、各行の一番右に表示されている元によって生成される部分群が存在するということである。具体的な形を知りたければ、それぞれの部分群に対してlist関数を実行すればよい。
sage: for H in S3.subgroups(): # python風のfor文 ....: H.list() ....: [()] [(), (2,3)] [(), (1,2)] [(), (1,3)] [(), (1,2,3), (1,3,2)] [(), (2,3), (1,2,3), (1,2), (1,3,2), (1,3)]
これで全ての部分群の具体的な元を求めることができた。
多項式のガロア群を求める
最初の例
さて、こちらはちょっと難しい。正直まだ完全に消化できていないので、分かっているところまで書いてみる。
多項式のガロア群を求めるには、まず多項式を指定し、かつその多項式の根を添加して得られる体を取得しなければならない。これにはNumberField関数を使用する。
sage: K.<alpha> = NumberField(x^2 - 2)
上記コマンドにより、という多項式の根であるを添加して得られる体を取得できた。式中のalphaはどうも根が入る変数のようで、いろいろいじってみるとどういうものか分かる。
sage: alpha alpha sage: alpha^2 2
ただし、このalphaの正体が実はよく分かっていない。これについては後述する。
さて、以下のコマンドにより、得られた体がガロア拡大体かどうかが分かる。
sage: K.is_galois() True
実行結果がTrueと出たので、これはガロア拡大体のようだ。これでやっとガロア群を求めることができる。体Kのガロア群は以下のコマンドで計算できる。
sage: G = K.galois_group() sage: G Galois group of Number Field in alpha with defining polynomial x^2 - 2 sage: G.list() [(), (1,2)] sage: G.order() # 位数も計算できる 2
以上により、の根を添加した体のガロア群が計算できた。
円分多項式のガロア群
次に、という円分多項式のガロア群を計算しよう。実際にやってみると、以下のようになる。
sage: K.<alpha> = NumberField(x^5 - 1) ・・・・(大量のエラーメッセージ)・・・・ ValueError: defining polynomial (x^5 - 1) must be irreducible
というわけで、失敗してしまった。エラーメッセージを見ると、多項式はirreducibleでなければならないとある。この単語の意味を調べてみたところ、「既約」ということだった。つまり、引数に与える多項式は上既約でなければならないようだ。
実は、sageを使うと多項式の因数分解も簡単に行うことができる。以下のようにすればよい。
sage: x = QQ['x'].0 # xを有理数体上の多項式環の変数にするための記法 sage: f = x^5 - 1 sage: f.factor() (x - 1) * (x^4 + x^3 + x^2 + x + 1)
これで上既約な2つの多項式が得られたため、これらについて再度ガロア群を求めてみる。ただ、の方は根が1であり、となるため無視してよい。よってについて計算してみる。
sage: K.<alpha> = NumberField(x^4 + x^3 + x^2 + x + 1) sage: K Number Field in alpha with defining polynomial x^4 + x^3 + x^2 + x + 1 sage: alpha alpha sage: alpha^2 alpha^2 sage: alpha^3 alpha^3 sage: alpha^4 -alpha^3 - alpha^2 - alpha - 1 # alphaは入力された多項式の根なのでこうなる sage: K.is_galois() True # ガロア拡大体!
どうやらこれはガロア拡大体のようなので、ガロア群を求めてみる。
sage: G = K.galois_group() sage: G Galois group of Number Field in alpha with defining polynomial x^4 + x^3 + x^2 + x + 1 sage: G.list() [(), (1,2,3,4), (1,3)(2,4), (1,4,3,2)]
よって位数4のガロア群が得られた。元々の多項式は円分多項式なので、これは巡回群となっている。しかし、これだとパッとみてそのことがよく分からない。そこで、galois_group関数の引数を変えて実行すると、もう少し分かりやすくなる。
sage: G = K.galois_group(type = 'pari') # 内部的にpariというソフトウェアの計算エンジンを使用している?? sage: G Galois group PARI group [4, -1, 1, "C(4) = 4"] of degree 4 of the Number Field in alpha with defining polynomial x^4 + x^3 + x^2 + x + 1
最後の行にC(4)と出力されているが、これはGが4次の巡回群であることを表している。念のため4次の巡回群を出力するコマンドと結果を比較すると、当然ながら一致する。
sage: CyclicPermutationGroup(4).list() [(), (1,2,3,4), (1,3)(2,4), (1,4,3,2)]
ガロア拡大体にならない例
最後に、ガロア拡大体にならない例について取り上げてみる。入力に使う多項式はおなじみのである。
sage: K.<alpha> = NumberField(x^3 - 2) sage: alpha alpha sage: alpha^2 alpha^2 sage: alpha^3 2 sage: K.is_galois() False
is_galois関数の出力がFalseになっており、これはガロア拡大体ではないことが分かる。実際に計算してみると、確かに失敗する。
sage: G = K.galois_group() ・・・・(大量のエラーメッセージ)・・・・ TypeError: You must specify the name of the generator.
最後のエラーを見ると、何やらgeneratorを指定せよとある。Generatorというのは恐らく生成元のことだと思うのだが、これを指定せよというのはどういうことだろうか?
これまでの例では、代数体Kを生成する際、変数としてはalpha1つだけを指定し、これが多項式の根になっていた。最初の例ではガロア拡大体を扱っていたわけだが、これはにalpha = だけを添加すれば得ることができた。また、次の例ではにを添加することでを得ていた。つまり、どちらも元を1つ添加することでガロア拡大体が得られていたので、特に問題はなかった。
しかし、の場合、ここからガロア拡大体を得ようとすると、となるため、2つの元を添加する必要がある。にも関わらず、最初に指定した変数がalphaだけなので、添加すべきものが足りないと言っているのではないかと思われる。
ここで疑問なのだが、そもそもalphaとは何者なのだろうか?多項式の根というのであればの3通りが考えられるわけだが、一体どれなのだろうか?どれでもよいのだろうか?もしくは、どれでもないのだろうか?ここがよく分からない。
ここでいろいろと足掻いてみたところ、以下のようなコマンドが動作することを発見した。
sage: G.<beta> = K.galois_group() # Generatorが欲しければくれてやる!Betaを持ってけ! sage: G Galois group of Galois closure in beta of Number Field in alpha with defining polynomial x^3 - 2 sage: G.list() [(), (1,2,3)(4,5,6), (1,3,2)(4,6,5), (1,4)(2,6)(3,5), (1,5)(2,4)(3,6), (1,6)(2,5)(3,4)]
よくよく出力を見ると、"Galois closure"がどうとか書いてある。これはガロア閉包のことだと思われるが、これをどう解釈したらよいのか?さらに調べてみると、galois_closureなる関数があったので、これとの出力を見比べてみた。
sage: L.<beta> = K.galois_closure() sage: L Number Field in beta with defining polynomial x^6 + 108 sage: G = L.galois_group() sage: G Galois group of Number Field in beta with defining polynomial x^6 + 108 sage: G.list() [(), (1,2,3)(4,5,6), (1,3,2)(4,6,5), (1,4)(2,6)(3,5), (1,5)(2,4)(3,6), (1,6)(2,5)(3,4)]
どうやら先ほどの出力と一致しているが、という怪しげな多項式が登場した。これは一体何なんだ?わけも分からずbetaをいじくってみると、以下のような結果が得られた。
sage: beta (1,2,3)(4,5,6) sage: beta^2 (1,3,2)(4,6,5) sage: beta^3 () # betaを3乗したら単位元に戻った
betaを3乗して単位元に戻るというのは、いかにもを彷彿とさせるわけだが、今回はこれ以上分からなかった。
ちなみに、typeをpariに指定すれば、このように苦しまずともガロア群が得られるようだ。
sage: G = K.galois_group(type = 'pari') sage: G Galois group PARI group [6, -1, 2, "S3"] of degree 3 of the Number Field in alpha with defining polynomial x^3 - 2
以上によりガロア群は3次対称群であることがわかった。
まとめ
今回はsageの持つ機能のうちほんの一部を触ってみたわけだが、実際には山のように機能があり、大変優れたソフトウェアのようだ。ただし、今の自分の数学力では、まだまだ使いこなすには至らず、無念であった。
教科書で理論を学ぶだけでなく、具体例を考えることの重要性は多くの人が理解しているところだと思うが、このようなツールはそれを助けてくれるという意味で、非常に重要なものだと思う。今後も機会があれば積極的に使っていきたい。
体K上の多項式環K[x]を既約でない多項式f(x)で生成されるイデアル(f(x))で割って得られる剰余環はなぜ体にならないのか
Kを体とする。K上の多項式環K[x]に対して、]がK上既約であれば、剰余環は体となる。これは代数学における極めて有名な事実だ。このようになる教科書的な説明を述べると、K上既約な多項式から生成されるイデアルは極大イデアルであり、極大イデアルによる剰余環は体になる*1から、ということになる。
しかし、ちょっと待って欲しい。多くの人はこれだけ見て「ああなるほどね」と納得するのだろうか?例えば、だとすると、これはK上既約ではないわけだが、このときが体にならないことは当然だと、直感的に理解できるだろうか?少なくとも、私はできない。
というわけで、本稿ではなぜが体にならないのかということを直感的に説明してみたいと思う。
このことを理解するために、1つ簡単だが重要な事実がある。それは「体は整域である」ということである。簡単に証明してみる。Kが体であり、かつとなるa, bが存在すると仮定する。すると、Kは体なのでaの逆元が存在する。このとき、となり、であることに矛盾する。よってKは整域である。
さて、だとすると、の元はと書ける。すると、である。この剰余環の積の演算を用いてこの元を2乗すると、となる。よって剰余環は整域ではないため、体ではない。
どうしてこんなことになってしまうのだろうか?K上の多項式をで割った余りは高々1次式であるが、は既約ではないため、1次式の積として書き表すことが出来てしまう。すると、その1次式同士を掛け合わせると、の倍数に出来てしまうのである。で割り切れる多項式はこの剰余環の零元であるため、整域ではなくなってしまうのである。
逆にf(x)が既約多項式であれば、f(x)より次元の小さいどんな多項式同士を掛けあわせてもf(x)の倍数にはならず、結果として剰余環は整域となる。これが、既約多項式で生成されるイデアルによる剰余環が体になる直感的理由である。(厳密な証明ではない。)
以上、定理が満たされないケースを深く考えてみることで、逆に定理をより深く理解することを試みた。特に代数学のように抽象的な分野では、具体例をたくさん考えて、自ら手を動かすことが理解への近道である。その手間を惜しむことなく、今後も数字と戯れていきたい。
*1:この証明は難しくはないが、ちょっとだけ複雑なので調べてみて欲しい。
ネットワークトポロジーに潜む位相空間
情報を学んだ事のある人間であれば、ネットワークトポロジーという言葉を聞いた事があるだろう。これは、ネットワーク上でサーバやスイッチ等がどのように接続されているかを示す用語である。
また、トポロジーというのは数学の位相を意味するということは、数学を深く学んでいない人でも何となく聞いた事があるだろう。
そこで思ったのだが、ネットワークトポロジーと言うからには、そこに何らかの位相空間があるはずである。しかし、いろいろ調べてみても、どうにも情報界隈でキチッと決められた位相構造の定義は無いように思われる。そもそも情報、特にネットワークを専門とする人で、位相空間をしっかり学んだことがある人は少ないような気がするし、この状況はある意味当然なのかもしれない。ただ単に、ネットワーク上でのノードの繋がり方が何となく位相空間っぽいと思った人が名付けたのかもしれない。
以上を鑑みて、ここ最近ネットワークの中にはどのような位相構造があるのかを数学的視点から真面目に考えていたのだが、考えがまとまってきたので記事にしてみたいと思う。*1
まず、ここで扱うネットワークとはどのようなものか定義する。ネットワークとは、有限なn個( )のノードを持ち、ノードの間がエッジで接続されているものであるとする。任意の2つのノードを直接つなぐエッジはあっても良いしなくても良い。また、任意の2つのエッジは、ノード以外の点で共有点を持たないこととする。1つのエッジが大きくよじれて、自分自身とクロスすることもないとする。さらに、ここでは純粋にノード間の繋がり方のみに注目したいので、全てのエッジの長さは1とする。これにより、ネットワークは距離空間となる。これはよくある議論で、ノード間のホップ数を距離とするのである。(この距離の考え方は後で拡張する。)
次に、数学における位相空間の定義に触れたいと思う。位相空間とは、ざっくり言うと「集合に対して開集合となる部分集合を定義することで作られる空間」である。開集合を定義するというのは、慣れないとちょっと不思議に思うかもしれない。ユークリッド空間では距離の概念があったから、開集合は自然に定義された。しかし、位相空間の考え方は、距離の定義されていない一般の集合に対して、逆にどのような部分集合が開集合であるかを決めてやることで、距離空間と似たような議論ができるようにするというものである。つまり、開集合さえ決まれば位相構造が決まると言っても過言ではない。
そこで、以下の2点を解決すれば、ネットワークの位相構造を決めることができる。
- ネットワークはどのような集合で表現できるか?
- ネットワークを表す集合において、どのような部分集合が開集合になるか?
まずパッと思いつくのは、i番目のノードをaiとした時、とするものである。このようにネットワークを離散的に捉えるのはよくある手法であるが、この場合、エッジはどのように表現されるのだろうか?
最初に考えたのは、開集合の決め方によってノード間の接続を表現する方法である。位相空間における開集合は、点の近傍を表していると捉えることができるので、ある点に接続されている全ての点とその点自体から成る集合を開集合とするのである。
一見するとこれは良さそうに見えるのだが、開集合の公理から、開集合同士の共通部分、および和集合も開集合になるため、ほとんどのケースでXは離散位相空間になってしまう。これでは全ての点がバラバラになってしまい、ネットワーク内の連結が表現できない。
調べてみると、エッジをノードと同じように集合の要素として扱うことを考えた人もいるようである。しかし、自分には長さを持つエッジをノードと同一視しているのがどうにも気持ち悪く、納得できなかった(追記2を参照)。興味のある方は以下を参照して頂きたい。
グラフ構造で位相空間のイメージをつかむ - Qiita
次に考えたのが、ネットワークをエッジも含めて3次元ユークリッド空間内に埋め込む方法である。ネットワークとは実際の空間にあるモノ同士の接続なのだから、3次元ユークリッド空間内にノードを表す点、及びエッジを表現する、点の間をつなぐ曲線を配置することができる。エッジの長さが全て1という制約はあるが、エッジは好きにたわませれば良いので、ノード数が有限であればこのような集合を構成することは可能である。
では、ここにどのような開集合系を定義することができるだろうか?ここで定義した集合はユークリッド空間の部分集合なので、私は最初次の定理を利用することができると考えた。
位相空間Aが集合Bを部分集合として含むとする。Aの任意の開集合Uに対して、はBの開集合となる。
一度はこれで決着かと思われたが、実はこの開集合系にはまだネットワークを表現するには不自然な点がある。例えば、以下のようにエッジがたわんだネットワークを考えよう。
ここで、点のε近傍を考えると、これは開集合である。そのため、UかつXは開集合である。しかし、そうなると以下の図の赤色で示す部分がXのε近傍となる。
ノード間の距離はエッジに沿って考えるのが自然なので、上のような集合がε近傍となるのは不自然である。
次に考えたのが、ノードを表すある点からエッジを表す曲線に沿って長さε未満の部分をε近傍とする方法である。以下に例を示す。
ここで再び開集合の公理より、開集合同士の交わりは再び開集合になるので、ノードの真ん中にポツンと開集合ができてしまう。
ここではこのような開集合も受け入れることとする。
また、(あまり意味はないが)位相空間足り得るためには、エッジの途中の点の近傍というものも考える必要がある。例えば、点とを繋ぐエッジにおいて、から距離d(d<ε)だけ離れた点を取ると、ここでのε近傍は以下のようになる。
また、もともとはノード間でしか距離は考えていなかったが、近傍を考えるためにはエッジの途中の点の間にも距離が生まれるが、これも認めることにする。
ここで考えたようなε近傍が本当に開集合かどうかを調べるのは簡単である。ネットワークの集合をXとすると、ε近傍として決めた曲線Vを薄く包み込むような3次元ユークリッド空間上の開集合Uを考えれば、は先ほど述べた定理により開集合である(追記1を参照)。
さて、先ほどからやたらとε近傍にこだわっていたわけだが、ε近傍だけが開集合ではない。しかし、距離空間において、ε近傍を全て集めたものは開基と呼ばれ、これらの和集合を全て集めたものを加えてやれば、それが開集合系を成すことが知られている。その意味で、ε近傍だけを定義すればほとんど開集合系を定めたことになる。
以上により、ひとまずネットワークを表現する集合、及びその開集合系を定めることができた。
さて、ここからは私の自己満足である。上で定義したネットワークの位相構造は、エッジがグニャグニャと(ある程度自由に)曲がることができて、どうにも汚い印象がある。例えるなら、整理されていないサーバラックの裏側を覗いたような残念な気持ちになるのである。これをもう少し"綺麗に"配線することは出来ないだろうか?
最も綺麗な配線は、全てのエッジを真っ直ぐな線分にすることである。しかし、全てのエッジの長さが1であるという制約を考えると、ノードの数が増えた場合にこれは実現不可能である。もしノード数が3つなら正三角形の、4つなら正四面体の各頂点にノードを配置することで実現できるのだが・・・
そこで考えた。次元を上げたらどうなるか?今、2次元空間では3つの点、3次元空間では4つの点を、互いに長さ1の線分で繋ぐことができるのだから、n次元空間ではn+1個の点を長さ1の線分で繋げられるのではないか?
調べてみたら、この予想はなんと正しいことがわかった。詳細な説明は以下のリンクを参照して欲しいが、ようはn次元空間での超正多面体を考えるのである。そして、その中でも全ての頂点が互いに辺で結ばれるような超正多面体はnがいくつであっても存在する。
http://eprints3.math.sci.hokudai.ac.jp/364/4/jin0804.pdf
具体的な形についても述べておく。n+1次元空間において、というn+1個の点を互いに結ぶことで、n次元の部分集合が得られる。これこそが上で述べたn次元の超正多面体となる。
この超多面体の頂点にノードを配置することで、全てのエッジを長さ1の線分として表し、かつノードも対称な形で配置できる。
さて、これで理想的なネットワークの位相構造を手に入れたのであるが、ここでやりたいことは、3次元ユークリッド空間上の汚いネットワークを、この綺麗なネットワークに対応付けることである。そうすれば、3次元ユークリッド空間上の全てのネットワークに対して標準形のようなものを与えることができる。
この対応を探すことは、まさに両者の間の位相同型写像を探すことに他ならない。位相同型写像とは、連続な全単射であり、かつ逆写像も連続であるような写像のことである。証明は省くが、何次元の空間であろうと点は点(0次元)であり、線は線(1次元)なのだから、両者が位相同型であることはほとんど明らかであろう。
以上、ネットワークトポロジーを3次元ユークリッド空間上に埋め込む形で定義し、かつその標準形を高次元のユークリッド空間上に与えた。数学を学んだことで、情報の世界で長年謎だった問題が解決され、数学を学ぶモチベーションがさらに高まった。これからも数学に強いエンジニアを目指し、日々数学を学んでいきたい。
追記1
ネットワーク集合自体はユークリッド空間に埋め込まれているとは言え、この集合上で考える距離はもはや通常の意味での距離とは異なるため、近傍もユークリッド空間とは違うものになる。そのため、ユークリッド空間の開集合との共通部分だということを利用して開集合であることを主張するのは誤りだと気づいた。素直にノード上をたどった長さを距離として、それを用いて開集合を決めるのが自然であろう。
追記2
本稿を書いてからずっと悩んでいたが、やはり離散的な構造であるグラフを連続的な空間に埋め込むというのは、なんとも美しくないような気がしてきた。悔しいが、リンクを貼った先の記事で紹介されているような位相の入れ方がよいのかもしれない。ただし、やるならとことん抽象的にやるべきである。すなわち、ノードとエッジはどちらも本質的には区別のない点であると捉え、ノードに対応する点の近傍にはそれとつながるエッジを含め、エッジに対応する点の近傍はそのエッジのみから成る集合であるとする。そうして、ノードだのエッジだのの区別がなくなった点に対して、今度は逆に開集合として自分自身だけが含まれるようなものが存在する点はエッジであり、そうでない点はノードであると考えるのである。紹介した記事とほとんど同じことを言っているようだが、ノードとエッジを本質的に区別するのは位相構造のみであるという立場を強く強調しておきたい。
*1:本記事に記載している内容は私が自力で考えて導き出したものであり、これが必ずしも正解とは限らない。そういう考え方もあるのだと思って頂ければ幸いである。