数理解析研究所講究録
第 1907 巻 2014 年 90-96

90

アソシエーションスキームを利用した可移置換群の構成
宮本泉$*$IZUMI MIYAMOTO

山梨大学
UNIVERSITY 0F YAMANASHI

置換群

1

置換群 $G$ :対称群 Sym$(\Omega$ $)$の部分群、 $\Omega=\{1.2. \cdots, n\}$$1 iarrow^{j=i^{g}} n$$g\in G\subseteq Sym(\Omega)$$G$: 可移 (transitive)$\Omega$の任意の点$\Leftrightarrow$$i,$ $i$に対して、 $i^{g}=j$ とする $g\in G$ が存在

orbit

同型と共役

1.1

次の置換群 $G$ を含む同型類$n$$\Leftrightarrow$

対称群 Sym $(n)$ による $G$ の共役類 $G$ の $h\in Sym(n)$ による共役$G^{h}=\{h^{-1}gh|g\in G\}$

$G$の $H$ における正規化群(Normalizer)

Norm $(H, G)=\{h\in H|G^{h}=G\}$
正規化群計算、 2 つの部分群の共役判定 :次数$\langle\langle$$n$が小さくても計算が非常に困難な場合がある。

ここでの群の計算は、 数式処理ソフトウェアパッケージ GAP を使用

nmiyamotol@gmail.com$\rangle\rangle$$G^{h}$

91
1.2

置換群のデータ ( は Magma による)$*$$n NrTrans\dot{\ovalbox{\tt\small REJECT}}tiveGroups(n) NrPr\dot{\ovalbox{\tt\small REJECT}}m\dot{\ovalbox{\tt\small REJECT}}t\dot{\ovalbox{\tt\small REJECT}}veGroups(n)$$2011174$$21 164 9$

$2259
4$
$2425000
5$$2521128$$2696
7$$27239215$$28 1854 14$23(7)729(8)

831(12)

12$30 5712 4$$32 *2801324 7$1.3

固定部分群 (Stabilizer)$1 i=i^{g} n$$o_{g\in G_{i}}$部分集合$\Delta$の固定部分群

原始的な群 Primitive)$($$G_{\Delta}$$\Leftrightarrow$. . . (集合として、 または、 各点ごと)可移な群で、 1 点固定部分群【注】 可移な群では、 すべての$G_{i}$は、 互いに$G$$G_{1}$が $G$ の極大部分群の中で共役$M$$1 \Omega_{1} \Omega_{2} \Omega_{d}$$g\in G\Rightarrow\Omega_{i}^{g}=\Omega_{j}$92$\{\Omega_{1}, \Omega_{2}, \cdots \Omega_{d}\}:G$のブロツクシステム $\Rightarrow G\subseteq W=Sym(\Omega_{1})1Sym(d)$$M=G$ における集合$\Omega_{1}$(WreathProduct)の固定部分群【注】 素数次数の可移置換群は primitive

可移な群の分類の現状

1.4

Primitive な群の分類
GAP のデータ 2499 次まで ver4.7.2
Magma のデータ 4095 次まで ver219-2
可移な群の分類の現状
30 次以下 :10 年以上前、 確認に時間をかけている。Hulpke
32 次:Cannon-Holt 2008 年 12 月、 確認 2011 年 (Magma のデータ)

32 次の個数が多すぎて、Magma の通常の組込みデータにはできない。
それで、 分類はここで止まっている。 (前の表の通り)$33$ 、 $34$ 、 $35$

次は、 これまでの方法で簡単であろう。 36 次は、 それなりに、、、$\circ$$(arrow 33,34$ 次は “一応” 昨年、 35 次は今回)

分類に必要とされる関数は、 GAP システムに組込まれている。 これらを使って、 分かり易く分類したい。

30 次以下の場合の確認も含めて。
$arrow$

いろいろ場合わけした計算が必要となって、 分かり易いとは言い難い。

計算方法 :昨年と同様

2

アソシエーションスキーム

可移な群 $G$ から構成されるアソシエーションスキーム $A$$\Rightarrow G$の $\Omega^{2}=\{(i,j)|i,j\in\Omega\}$への作用の orbit 全体

このときは、$A$の自己同型群 $Aut(A)=TwoC\ovalbox{\tt\small REJECT} osure(G)$ が成立$TwoClosure(G)\Leftrightarrow$

The largest group $\subseteq Sym(n)$ which has the same orbits on$\Omega^{2}$as

$G$

has.

アソシエーションスキームの分類

次数 30 までと、 $32$、$33$ 、 $34$は分類済

35 次:2 つの場合、 固定部分群
分類可$arrow$$G_{1}$$Aut(A)$ の計算は簡単の orbit のサイズが、 1, 4, 12, 18 と 1, 6, 12, 16 となる場合以外はこれらの場合のみ、 プログラムを修正して可移群を計算

計算方法 :同じアソシエーションスキームを作る $G=TwoClosure(G)$ ごとに分類$G$ の可移な部分群 $H$ で、 $G=TwoClosure(H)$ となるものをすべて生成異なるアソシエーションスキームを作る群は、 互いに同型にはならない。
今回の計算の主な改良点$\bullet$Complement
基本可換正規部分群$E\triangleleft G$

に対して、ComplementH の計算$G=EH,$$E\cap H=\{1\}$単位元のみの群93
この $H$ のなかから、 上の条件を満たすものを求める。

$\bullet$

部分群の同型判定構成された群のなかから同型類の代表を選び出す。

計算方法の改良点

3

計算方法 :改良点

Complement の計算

昨年 :Complementclasses $(G, E)$ を使用が一般の群、 とくに、 非可解 (solvable でない) 群でも使用可
ComlementH の $G$ による の中での共役類を計算
今回 :ComplementCIasses $(N, G, E)$ も使用
は可解、( は $N$ の正規部分群)、 $N$ も可解のとき
ComlementH の $N$ による の中での共役類を計算
$G$

$G$

$G$

$G\underline{\triangleleft}N$

$G$

$G$

計算方法 :改良点

Complement の計算
ComplementClasses の使用法
置換群 $N$ を PcpGroup に、 lsomorphismPcpGroup を使って変換

$G$、

$E$

は、 その部分群として設定【注]

GAP のマニュアルには、PcpGroup の説明はほとんど無い
群計算 最も簡単 PcGroup(Poly Cyclic Group、特に、 可解群)、$\eta$

次が、 置換群

IsomorphismPcGroup:可解群を PcGroup に変換

GAP の置換群 :群を、 部分群と設定して構成しなくても、 部分群かどうかの判定が可能(普通の考え方 :いくつかの置換群を取扱うとき、 適当な次数の対称群の中に、 部分群として構成する。
$arrow$群の相互の関係が計算可能になる。)

計算方法 :昨年

部分群の共役計算群の適当な属性を調べて、 得られた部分群全体を分割$arrow$

同型判定の対象となる群を制限元の個数 (位数) $|G|$ や、 $G$ の$\Omega^{3}$への作用のパターンなどで分割を作成

TransitiveGr up(次数，番号) GAP の置換群のデータ$\circ$$Trans\dot{\ovalbox{\tt\small REJECT}}tive\ovalbox{\tt\small REJECT} dent\dot{\ovalbox{\tt\small REJECT}}f\dot{\ovalbox{\tt\small REJECT}}cation(G)$$\Leftrightarrow G$

GAP が$arrow$

は$|$

$G$

$arrow$

番号$Trans\dot{\ovalbox{\tt\small REJECT}}t\dot{\ovalbox{\tt\small REJECT}}veGroup(n, 番号)$と同型 (共役)のなんらかの属性をしらべて、 同型判定をしていると考えられる。

それなりの時間がかかる。

27 次の可移群は全部で、 2392 個

94
本プログラムで 27 次の可移群生成 100 分 Transitiveldentification もすると 170 分アソシエーションスキームの自己同型群の利用$arrow$

得られた群 $H$ は、 すべて同じアソシエーションスキームを作る。
共役は、 アソシエーションスキームを構成する
で計算 ( TwoClosure は各 orbit ごとに固定)$\Omega^{2}$上の orbit を、 全体として固定する自己同型群のなか$rightarrow$

正規化群 $N=Norm(K, H)$ が、 $K$ の大きな部分群になるときの $N$ による coset の個数が多くないとき) $\leq 5000$($rightarrow K$$arrow$coset の代表$r$〜50000?)のすべてを使って、 $H$ の $G$ のなかでの共役 $H$ ‘のすべてを列挙。 部分群 $L$ が、 この$H^{r}$のなかに存在しなければ共役にはならない。
計算方法 :改良点 部分群の共役計算

coset の代表

$r$のすべてを使って、 $H$ の $G$ のなかでの共役 $H$ ‘のすべてを列挙。 ソートしておく。

構成された部分群全体もソートしておく。
この 2 つの部分群の列をマージして、 一致する群を求める。 $arrow H$ と共役となる群が得られる。

互いに共役かどうかの計算すべてが互いに共役のときはこれで計算完了
部分群の属性 :交換子群の系列 (DerivedSeries)$H\geq H’\geq H"\geq\cdots$(この系列の長さ、 現れる群の位数を使って、 分割を細分する。)

この系列の真ん中くらいの群 $D$ を使う。

得られたすべての部分群 $H$ にたいして、 この群 $D$ をリストアツプして、 その共役計算を行う。
利点$\bullet$$D$($\bullet$

は $H$ に比べて小さい。 このことからは、 互いに共役となる $D$ の個数が増えることも期待できる。

$arrow D$の共役計算は、 すべてが共役の場合に近くなり計算が楽。)

共役でない $D$ をもつ $H$ 達は、 互いに共役にならない。
$\Leftrightarrow$

共役な $H$ 達は、 共役な $D$ をもつ。

95
coset を利用した共役計算の改良
共役な $D$ 達を、 1 つの $D$ に共役をとって移す。
アソシエーションスキームの自己同型群を $K$$arrow$、$N=Norm(K, H)$ とする。

この $D$ をもつ $H$ 達の共役は、 Norm $(K, D)\leq K$ のなかで決まる。

【注】 $N=Norm(K, H)\leq Norm(K, D)\leq K$$c=K$ の $N$ による coset の個数$c_{1}=K$ の Norm $(K, D)$ による coset の個数$=\prime C=c_{1}\cross c_{2}$による coset の個数$c_{2}=$
Norm $(K, D)$$c>50000$ で、 $H$ の共役計算に coset を使えない場合でも、の $N$使って計算してから、$c_{1},$$c_{2}\leq 5000$となって、 $D$ の共役を coset をの共役も coset を使って計算することが期待できる。

$H$

計算結果

4昨年

33 次
34 次

計算時間 12(報告集では修正済)

157 個

102 個

$\sim$3分

計算時間 3 分

同じプログラムを、 $27$、$28$ 、$30$

最長計算時間 11 分

最長計算時間 1.6 分
次で動かしているが、、、$\circ$

今回

33 次

162 個

計算時間 4 分余、 最長計算時間 2 分34 次115 個

計算時間 10 分余、 最長計算時間 4 分 (2 個)

35 次405 個

計算時間 5 分30 次以下の場合、 本プログラムで可移置換群の分類を再確認

32 次の再確認では、、、。
32 次の可移群の確認

32 次のアソシエーションスキームの 1 つから構成される可移群の個数
計算時間 (単位 :時間)
可移群

スキーム

as32[5471]
as32[4505]
as32[6062]$as32[3945|$

as32[4525]$as32[7782]$$as32[8596]$

as32[4205]
as32[6472]
as32[5607]

278,578 個
274,618 個
223,344 (固212,891 個
158,755 個
151,879 (固124,093 個
105,319 個
91,298 個
68,822 個

残り :アソシエーションスキーム

16 個

278.6
64.0
56.9
73.9
46.437.6
30.7
20.3
21.9
16.5

3 つの部分に分けて計算 (個数最大)
2 つの部分に分けて計算

可移群

216,412 個

96