お試し計算群論演算表から群の位数を求める−その1 - Finite Groups Fun 有限群あるいはちょこっと計算ファンの日記

群論の計算を計算機にやらせてみようという企画の手始めとして，群の演算表が与えられたときにその群の位数を計算するというプログラムを考えてみる。群の元が1から番号をつけられているとして（1番目は常に単位元としておく），演算表が1から $N$ までの整数をエントリーのもつ $N\times N$ の行列として定義されているとする。この場合，普通は群の位数は $N$ なわけであるが，番号がつけられた元のいずれかが等しくなってしまうケースも想定する。つまり，

縦もしくは横のエントリーに重複がある
結合律 $(ab)c=a(bc)$ の両辺の番号が一致しない

このようなことが起こった場合その2つの元を同じ元と見なして，演算表を縮小していく．これを繰り返して上記の不整合がなくなった時，それは演算表として正しく群の定義に従うもの（単位元、逆元の存在、結合律を満たす）になるが、そのときの演算表の大きさを最初に与えられた演算表が定める群の位数であると定義する．しかし，生成元の消去操作の順番に任意性があるため，これがwell-definedなのかという点が問題である．
まず $N$ 個の生成元を持つ自由群 $F$ を最初の演算表で与えられる $N\times N$ 個の関係式（が作る正規部分群）で割ったものが今考えている群 $G$ の（大元の）定義である．上記の操作で得られた群のひとつを $\tilde{G}$ とする． $\tilde{G}$ での元の関係は $G$ の元の関係から導かれるものの一部であるから，全射準同型 $\phi:\tilde{G}\to G$ が存在する．一方， $\tilde{G}$ では，最初の演算表が満たされているため， $G$ のuniversalityから，準同型 $\psi:G\to \tilde{G}$ が存在するが，生成元の対応を見ればこれは全射となる． $\tilde{G}$ と $G$ は互いに全射準同型が入るので位数を比較すれば同型であることが分かる．

プログラム言語としては，まったく個人的な趣味で Schemeを使う。（理由は一度使ってみたかったから...）

さて，なぜこんなものを作ろうとしているのかであるが，ひとつの中間ゴールとして，与えられたPCP(Power-Commutator Presentation)に対してそれが定義する群の位数を求めてそのconsistencyを判定したいのである．2-群で生成元が3つの場合で具体例をあげてみよう．（PCPの関係式として明示していないものはすべて1となるものとする．i.e. $a_2^2=1,\quad [a_3,a_1]=1$ 等．）

例
[tex:G_1=]
[tex:G_2=]

PCPが与えられた時，たとえば必ず積の文字列の前から計算するというルールを使うことでその演算表を計算することができる(いずれは計算機にやらせるつもりだが，今回はせこせこと手計算した...)．上の例では次のようになっている（元の名前は，単位元=1， $a_1=(100)=2$ ， $a_2=(010)=3$ ， $a_1a_2=(110)=4$ ， $a_3=(001)=5$ 等である）．

$G_1$	1=(000)	2=(100)	3=(010)	4=(110)	5=(001)	6=(101)	7=(011)	8=(111)
1	1	2	3	4	5	6	7	8
2	2	5	4	7	6	1	8	3
3	3	8	1	6	7	4	5	2
4	4	3	2	1	8	7	6	5
5	5	6	7	8	1	2	3	4
6	6	1	8	3	2	5	4	7
7	7	4	5	2	3	8	1	6
8	8	7	6	5	4	3	2	1

$G_2$	1=(000)	2=(100)	3=(010)	4=(110)	5=(001)	6=(101)	7=(011)	8=(111)
1	1	2	3	4	5	6	7	8
2	2	7	4	5	6	3	8	1
3	3	8	1	6	7	4	5	2
4	4	1	2	3	8	5	6	7
5	5	6	7	8	1	2	3	4
6	6	3	8	1	2	7	4	5
7	7	4	5	2	3	8	1	6
8	8	5	6	7	4	1	2	3

各エントリは縦横の重複は無く，一見したところ何か問題があるようには思われない．しかし，実際のところ $G_1$ は $C_4$ の $C_2$ による半直積であり，その位数は8となるが，一方， $G_2$ は関係式から $a_3=1$ が導出されてしまい $C_2\times C_2$ になるため，位数は4となる．つまり， $G_2$ の演算表は結合律を満たしていないのである．たとえば $a_1^3$ を $(a_1^2)a_1$ と $a_1 (a_1^2)$ の二通りの計算で実行してみれば、演算表から 4=8 すなわち $a_1 a_2=a_1 a_2 a_3$ が導出されてしまう．しかし演算表からすべての3項の組み合わせで結合律を手計算で確認するのは大変なので，手始めにまず結合律が成立しているかどうかチェックするプログラムを作ってみた．

- - - - -

(define group-operation-table1 
  (vector
   (vector 1 2 3 4 5 6 7 8)
   (vector 2 5 4 7 6 1 8 3)
   (vector 3 8 1 6 7 4 5 2)
   (vector 4 3 2 1 8 7 6 5)
   (vector 5 6 7 8 1 2 3 4)
   (vector 6 1 8 3 2 5 4 7)
   (vector 7 4 5 2 3 8 1 6)
   (vector 8 7 6 5 4 3 2 1) ))

(define group-operation-table2 
  (vector
   (vector 1 2 3 4 5 6 7 8)
   (vector 2 7 4 5 6 3 8 1)
   (vector 3 8 1 6 7 4 5 2)
   (vector 4 1 2 3 8 5 6 7)
   (vector 5 6 7 8 1 2 3 4)
   (vector 6 3 8 1 2 7 4 5)
   (vector 7 4 5 2 3 8 1 6)
   (vector 8 5 6 7 4 1 2 3) ))

;2つの元の積を返す
(define (product v i j)
  (vector-ref (vector-ref v (- i 1)) (- j 1)))

;3項の積の比較結果を返す
(define (compare-product v i j k)
  (= (product v (product v i j) k) (product v i (product v j k))))

;3項演算結果の表示
(define (display-three-items v i j k)
  (display "((" ) (display i) (display " ") (display j) (display ")") (display k) (display ")=")
  (display (product v (product v i j) k))
  (display " (" ) (display i) (display "(") (display j) (display " ") (display k) (display "))=")
  (display (product v i (product v j k) ))
  (newline))

;結合律のチェック
(define (check-associativity v)
  (let ((n (vector-length v)))
    (do ((i 1 (+ i 1))) ((> i n) ())
      (do ((j 1 (+ j 1))) ((> j n) ())
        (do ((k 1 (+ k 1))) ((> k n) ())
          (if (compare-product v i j k) () (display-three-items v i j k) ))))))

- - - - -

これで

(check-associativity group-operation-table1)

を実行すれば， $G_1$ の演算表が結合律を満たすことが確認できる．

また、

(check-associativity group-operation-table2)

を実行すれば，

((2 2)2)=4 (2(2 2))=8
((2 2)4)=2 (2(2 4))=6
((2 2)6)=8 (2(2 6))=4
((2 2)8)=6 (2(2 8))=2
((2 4)2)=6 (2(4 2))=2
…

などの $G_2$ の演算表の結合律が成立していない所を表示してくれる．