計算群論事始

前回述べたBescheらのミレニアムプロジェクト等々、コンピュータを使って有限群論を研究するという分野はCGT（Computational Group Theory）と呼ばれている。ルービックキューブの最小手順を求めたりするお遊び風のものもあれば、化学で高分子の異性体の数を数えたりとか実用的な応用もあるそうだ。純粋数学向けとしては、有限群のデータベースを使って、何か証明したいことが本当に正しそうかあたりをつける実験をやったりするのに使われているらしい。
私の当面の興味は、位数の小さな群、特に位数16,32,64...の群の数を数えることであるが、この計算には、p-group Generation Algorithmという方法があり、位数256以下までならこれで計算できるという。このアルゴリズムはNewmanらが1977年ごろ開発したものであるが、Webで解説などを探したが詳しい情報は得られなかった。
そこで、よく参考文献にあげられているO'Brienの論文『The p-group Generation Algorithm』にあたってみようとWebで探したところ、O'BRIENで入手することができた。学術論文の入手にいつも苦労する素人としてはこういったWeb掲載はとても助かる。（以前日記に載せていたちょっと怪しいリンクから、著作者ご本人のサイトに変更．と思ったらいつの間にか中身が消滅しているので、元のリンクも残しておきます．CGT）
論文の最初の「この論文に詳しく書いたから、これを読めばプログラムが作れるよ」という甘い言葉につられてさっそく解読を始めてみたが、これが結構難しい。アルゴリズムの数学的バックグランドも複雑であるし、また、プログラムの流れの概要に「与えられたGに対するAut(G)の全ての生成元αについて、これこれを計算...」とさらっと書いてあったりする。けっこう食えないかも。ともあれ、解読結果はぼちぼちとこの場で紹介していきたい。