読者です 読者をやめる 読者になる 読者になる

群の可視化に関する考察

私は元来情報系の人間であるが、ここ数年は専ら数学の勉強をするのが趣味となっている。個人的な最終目標は代数的整数論、及び解析的整数論の基本的な事項を理解することであるが、まずはそのための下準備として代数学を勉強している。

代数学における一番基本的な代数構造として、群と呼ばれるものがある。集合Gに対して二項演算が1つ定義されており、かつ以下のような性質を持つとき、Gを群と呼ぶ。(あまり正確な言い方では無いかもしれないが、ざっくり理解する上では大丈夫だと思いたい。)

  1. 単位元と呼ばれる元eがあり、任意のg∈Gに対してeg=ge=gとなる。
  2. 任意のg∈Gに対して逆元と呼ばれる元g^{-1}∈Gがあり、gg^{-1}=g^{-1}g=eとなる。
  3. 結合法則が成り立つ。

演算が可換であることは群の定義に含まれないので注意が必要である。

さて、群の全容を知りたい場合は、通常全ての2つの元の間の演算結果を表に表す。以下に位数(群の要素数のこと)3の場合の例を示す。(ちなみに、位数3の群は下に示したものしか存在しない。多分。)

e g1 g2
e e g1 g2
g1 g1 g2 e
g2 g2 e g1

表の各セルの意味は、一番左の列に記された元aと、最上部に記された元bとの間で、abという演算を行った結果である。ちなみにこの例ではたまたま演算が可換となっているため、表が対角線に対して対称な形となっている。このような群を可換群、もしくはアーベル群と呼ぶ。

しかし、個人的にはこれではどうにもイメージが湧かない。そこで、何とか群を可視化できないかと考えた。今回はその可視化のためのアイディアを書き記し、実際にいくつかの群について可視化を行ってみようと思う。

まず、群というのは群に与えられた演算について閉じている。すなわち、あるg∈Gについて、任意のh∈Gと演算を行うと、hg∈Gとなる。上の表を見ても明らかなように、Gの位数がnの場合、gに対してn個の遷移先がある。そして、それらは全て異なる。(hg=igとすると、両辺に右側からg^{-1}をかけることでh=iとなるため。)よって、ある1つの元gに注目して、それにGに属する元を順に(左側から)かけたとき、それぞれがどこに遷移するかをグラフで表すことができたら、うまく可視化出来そうである。上の表について実際にやってみた結果が以下の図である。

f:id:peng225:20151115141605p:plain

この図では、ノード内に注目すべき元が描かれていて、その要素に対してエッジに描かれている元を左側からかけた場合にどこに遷移するかを表している。単位元eは特別扱いして二重丸で囲っているが、特に大きな意味はない。上で示した表との対応関係を述べると、注目している元が各列の一番上に示しているもので、Gの各元を左からかけたときの遷移先がその列の各セルの値となっている。

これは中々良い方法なのではないだろうか。もちろんGの位数がnのとき、ノード数n、エッジ数n^2となるため、nが大きくなると可視化するのがしんどくはなる。位数4くらいが限界か?

そんなわけで、ここでは位数4の群について、全て図を書いてみようと思う。ところで位数4の群にはどのような種類があるだろうか?1つはクラインの四元群と呼ばれるものであり、もう1つは巡回群である。巡回群とは、全ての元がある1つの元(これを生成元と呼ぶ)のべき乗で表されるような群のことである。(ちなみに上で示した位数3の群は巡回群となっている。g1^1=g1、g1^2=g2、g1^3=eとなるため。)これ以外には位数4の群は多分存在しないが、自信はない。さしあたりこの2つについて可視化を行ってみる。

まず、クラインの四元群を表で表すと以下のようになる。

e g1 g2 g3
e e g1 g2 g3
g1 g1 e g3 g2
g2 g2 g3 e g1
g3 g3 g2 g1 e

簡単に説明すると、全ての元の逆元が自分自身となっているような群である。これは巡回群でない最小の群である。これを可視化した結果を以下に示す。

f:id:peng225:20151115141610p:plain

なんとも美しい対称形になった。

お次は位数4の巡回群だ。まずは表で表してみる。

e g1 g2 g3
e e g1 g2 g3
g1 g1 g2 g3 e
g2 g2 g3 e g1
g3 g3 e g1 g2

これを可視化すると以下のようになる。

f:id:peng225:20151115150439p:plain

これはこれでまた別の対称性が見られて面白い。ちなみに生成元はg1であり、g1^1=g1、g1^2=g2、g1^3=g3、g1^4=eとなっている。

ここまでやってみて気づいたことがある。それは、このように群を可視化すると、部分群の候補が簡単に見つかるということである。部分群とは、群の部分集合で、かつそれ自体群となるようなもののことである。例えばクラインの四元群において、H={e, g1}は部分群となっている。どうやって分かるかというと、まず群である以上はeは含んでいる必要がある。そこで、eとg1を繋ぐエッジ以外を全て切断すると、eとg1だけからなるグラフ内における遷移は、eまたはg1をかけることだけによって成り立っている。つまり、演算について閉じていることになる。これは部分群となるための必要条件である。(教科書に載っている部分群となる条件とは若干異なるが、よくよく考えると結局同じ意味になる、と思う。)あとはこの切り取られた部分に全ての元の逆元が含まれていればこれが部分群になることが確定するのであるが(詳細は割愛)、この方法だとグラフが巨大になってきた場合にそこまでは分からないので、あくまで部分群の候補が分かるという言い方に留めている。

逆に部分群とならない例としては、H={e, g1, g2}が挙げられる。これは、e、g1、g2の間を結ぶエッジ以外を全て切断したとき、g1とg2の間を行き来するのにg3が必要だからである。ちなみに、位数nの部分群の位数は、必ずnの約数となる。今、クラインの四元群の位数は4で、集合Hの要素数が3なので、Hはそもそも部分群にはなり得ないのである。

今回の試みは概ね満足のいく結果となったが、eをかけたときのエッジが他のエッジと重なってしまうのが少々残念だった。これらの図は全てgraphvizというソフトを使って描いているのだが、なんとかエッジを重ねずに描く方法はないものか。