有限群の列挙＆分類
位数n<∞の群は有限種類しかなく，演算結果の一覧表（Cayley表）により記述できる．集合GとG内の2項演算・の組が群と呼ばれるためには，群の公理：
- 零元と呼ばれるある元eがあって，任意のxに対しxe=ex=x
- 任意のxに対しxの逆元と呼ばれる元yがあって，xy=yx=e
- 任意のx, y, zに対し (xy)z = x(yz)
を満たさなければならない．今，3元から成る群についてCayley表を書くと以下のようになる*1．
| * | 0 | 1 | 2 |
| 0 | 0 | 1 | 2 |
| 1 | 1 | 2 | 0 |
| 2 | 2 | 0 | 1 |
ここで零元を書くのに0を使った．
もちろん一般には複数通りのCayley表があり得るのだが，3元の場合は一意に定まる*2．この表を書く際，各公理に対応して以下の制約に注意した．
- 第1列と第1行目は零元との演算結果なので見出しを写すだけ
- 各行，各列には0, 1, 2が1つずつ現れなければならない
結合律は... えーと（ぉ
まぁ要するにこの作業は自動化できる．しかし1と2を置き換えただけの表，代数学の言葉で言えば同型な群をまとめて扱うことが必要でもある．しかし当面はそれを無視すれば，与えられたnに対し位数nの群のCayley表を全部探すプログラムは以下のようなものだ．
- n行n列の表を作る
- 1行目，1列目に 0, 1, ..., n-1 を入れる
- 左上から順に*3表を舐めて開いているマスを探す
- 開いているマスの属する行と列内のマスで使用済みの数を列挙する
- 使用済みの数を集合 {0, 1, ..., n-1} から除き，そのマスで使える数の集合を定める
- 使える数それぞれに対して表をコピーし，各コピーのマスに数を書き込む
- 次のマスへ進む
- マスが全部埋まったらそれは正しいCayley表なので印刷．埋まらないうちに，ある空のマスにおいて使える数が何もなかったら破棄．
まぁ動的計画法による改善とか枝刈りの余地が多そうなアルゴリズムだが，とりあえずRubyで書いて自分のノート*4で走らせてみた．
もちろん同型なCayley表の同一視などはできていない．2つのCayley表が同型かどうかを判定する効率的なアルゴリズムも考えなければならない．
それでも実行すると，「5元で56通り」を出すのに数秒，「6元で9000通り超」に4分，7元では一晩でも終わらない（ぉ
文献*5には同型を除いて何通りあるかが32元の群まで載っているんだが，この方法では埒があかないことは明らかだ．生成元と関係式から攻めるべきなのか？
ていうか結合律考慮してねぇ（ぉ
*1:HTMLの罫線は制御がめんどいので勘弁してくれ
*2:上のものはZにおいて普通の加算の代わりにmod 3の加算を入れたものと一致する．それはよくとかZ/(3)と書かれる．
*3:まぁ順番はどうでもいいが．
*4:Celeron 450MHz, メモリ64MB, OSはVine Linux Seed．nice値を-20にした．
*5:シャファレビッチ，代数学とは何か，シュプリンガー・フェアラーク東京
