PCPの例 - Finite Groups Fun 有限群あるいはちょこっと計算ファンの日記

定義だけではなんなので、具体的なPCPの計算を $D_8$ と $Q_8$ でやってみる。

$D_8=\langle a,b \| a^4=1,b^2=1,b^{-1}ab=a^{-1}\rangle$ を定義として、降中心列を計算すると、

$D_8 \triangleright K_1=\langle a^2 \rangle \triangleright K_2=1$

となる。それぞれの商群から生成元を選んでやると、たとえば $\{a_1=b,a_2=a,a_3=a^2 \}$ とすると、PCPは

$a_1^2=1,a_2^2=a_3,a_3^2=1,[a_2,a_1 ]=a_3,[a_3,a_1 ]=1,[a_3,a_2 ]=1$

となる。
$Q_8=\langle a,b \| a^4=1,a^2=b^2, b^{-1}ab=a^{-1} \rangle$ では、

$Q_8 \triangleright K_1=\langle a^2 \rangle \triangleright K_2=1$

となり、降中心列はよく似ているが、 $\{a_1=b,a_2=a,a_3=a^2 \}$ と選ぶと、PCPは

$a_1^2=a_3,a_2^2=a_3,a_3^2=1,[a_2,a_1 ]=a_3,[a_3,a_1 ]=1,[a_3,a_2 ]=1$

と、 $a_1$ のp-powerの項が一箇所だけ違うものとなる。

PCPを与えると群が決まるが、一般的には係数をうまく与えないと位数が $p^n$ より小さな群ができてしまう。位数がぴったり $p^n$ になる場合をconsistentなPCPと呼ぶ。PCPがconsistentでない場合には、 $a_{k}$ らによるベキによる表示の唯一性が成立していないので、ごりごり計算して群の演算表をつくり、結合法則と逆元の存在をチェックするとよい。この判定は計算機に乗せやすいので、PCPを列挙（これは有限個しかない）してその中からconsistent なPCPを選び出せば群の分類問題は解決？！

だったらO'Brienの論文もいらないのだが、具体的な計算でも分かるように $a_{k}$ の選び方によりPCPは変わる。つまり、確かにconsistentなPCPを集めれば与えられた位数のp-群を列挙することはできるのだが、その中には同型なものが山ほど入っているのである。計算群論で一番難しい問題の一つは、与えられた2つの群が同型か否かを判定することであり、たしか群の同型判定問題には一般的なアルゴリズムは数学的に存在しないことが証明されていたはずで、PCPの山から同型なものを選びだすことは困難なのである。