数理解析研究所講究録
第 1785 巻 2012 年 67-72

67

部分直積群の正規化群計算の高速化について
宮本 泉
IZUMI MIYAMOTO

山梨大学
UNIVERSITY OF YAMANASHI

1

部分群の共役と正規化群.
.

$G,$ $H,$ $K$

$H$

: 集合

$\Omega$上の置換群とする。と $K$ は $G$ において共役 $\Leftrightarrow g^{-1}Hg=K$ for some $g\in G$$H=K$ として、 $g^{-1}Hg=K$ とする$\Rightarrow H$の$G$$g$をすべて求めるにおける正規化群 Norm $(G, H)=\{g\in G|g^{-1}Hg=H\}$Cannon-Holt. “The transitive groups of degree 32“ 2008.12
Computing normalisers and testing conjugacy of subgroups are notoriously difficult problems
even in permutation groups of small degree.
【注】 ここでは、 正規化群計算と関連して、 共役に移す元を具体的に求める。

2.
.
.
.
.

Definitions and Notations$\Omega=\{1,2, \cdots, n\},$$n=G$ の次数 (degree)$G$の $i\in\Omega$ をふくむ $orbit\Leftrightarrow\{i^{g}|g\in G\}$

$G$

は$\Omega$

上、 可移 $(tmnsitive)\Leftrightarrow G$ は$\Omega$

上の orbit が 1 個$\Leftrightarrow\{i^{g}|g\in G\}=\Omega$

$G$

における点

$G$の$\Omega^{2}$$i$for any$i\in\Omega$の固定部分群 $\Leftrightarrow G_{i}=\{g\in G|i^{g}=i\}$上への作用 : $(i,j)^{g}=(i^{9},j^{g})$ for $(i, j)\in\Omega^{2}$ and $g\in G$【Fact】 $N=$ Norm $(G, H)$ とする。
$N$は $H$ の orbit の集合に作用。 $H$$G$のときは、 $H$,$A$$N$となることより、 $N$ の orbit は、 $H$ の同じサイズの orbit いくつかの和集合$\Rightarrow H$

imiyamotol@gmail.com

$N$

$A$

$G$

: 上の条件を満たす簡単に計算できる群を探す。

68
3

コピアラントコンフィグレーション
コピアラントコンフィグレーション $(\Omega, \{R_{i}\}_{i=0},12,\cdots,d)H$ の$\Omega^{2}$への作用の orbit$R_{4}$【例】 $\Omega=\{1,2,3,4,5,6\},$ $H=Group((1,5,4)(2,6,3), (1,6,3,2,5,4))$$R_{0}=\{(1,1), (2,2), (3,3), (4,4), (5,5), (6,6)\}$ ,$R_{1}=\{(1,2), (2,1), (3,4), (4,3), (5,6), (6,5)\}$ ,$R_{2}=\{(1,3), (1,4), (2,3), (2,4), \cdots, (6,1), (6,2)\}$上の orbit$\Omega$$\Omega$

4個,$R_{3}={}^{t}R_{2}=\{(3,1), (4,1), (3,2), \cdots, (1,6), (2,6)\}$2 3 4 5 6

1

$C=645321(_{2}^{1}3230$$033221$$032231$$033221$$303221$$033221]n\in Narrow(_{3}^{1}0322$$033221$$032321$$032231$$033221$$033221]$

コピアラントコンフィグレイションの自己同型$(032321$$033221$$033221$$330221$$303221$$323021)\cong(330221$$033221$$303221$$023321$$033221$$033221)$自己同型群 $Aut(C)=Group((3,5,4,6), (1,6,2,5)(3,4))\supsetneq H$$Aut(C)$ の$\Omega^{2}$上の orbit への作用 :馬， ,$R_{2}$$R_{1}$$\Leftrightarrow$$R_{3}$

命題 31

Norm $(G, H)$$Aut(C)$$Aut(C)$ は、 通常、 簡単に計算可能 (実験してみると、 これだけではあまり効果はない)

4可移な群の正規化群計算に使った方法[Assumption] $N$ が $H$ と、 共通の orbit $O$ をもつ。 $\Rightarrow N=<H,$ $N_{i}>,$ $i\in O$ が成立[Example] $\Omega=\{1,2, \cdots, 28\}H=$ TransitiveGrou (28, 1528), G SymmetricGroup(28)
$=$

$p$

$\Rightarrow\Omega$

は、 $H,$ $N$ 共通の orbit $\Rightarrow N=<H,$ $N_{1}>$点 1 の固定部分群$H_{1}$$\Rightarrow\{3,4, \cdots, 28\}$の orbit

は、{1}, {2}, 3, 4,$H_{1},$$\{$$N_{1}$$\cdots,$$28\}$

共通の orbit $\Rightarrow N=<H\iota,$ $(N_{1})_{3}>$正規化群計算 $N_{1,3}=(N_{1})_{3}$ は、 $H$ における点 1,3 の固定部分群, for all $n\in N_{1,3}$の正規化群) (Hl の正規化群)$n^{-1}H_{1,3}n=H_{1,3}$$\Rightarrow N=<H$,($H_{1,3}$$\cap$$\cap$

N$>$$H_{1,3}$を正規化する。

69
$H,$

$H_{1},$$H_{1,3}$の作るコピアラントコンフィグレイション $C,$$C^{(1)},$$C^{(2)}$の自己同型群 $A,$$A^{(1)},$$A^{(2)}$を計算する。
$|A|$$|A^{(1)}\cap A|$$=$$|A^{(1)}|$$|A^{(2)}\cap A^{(1)}\cap A|$$=$$|A^{(2)}|$$N=N(G, H)$$A$$2^{14}14!$

$=$

$=$

$2^{13}13!$

$=$

$=$

1428329123020800
51011754393600
196608$=$$<H$ , Norm $(A^{(2)}, H)>$$=$$<H$ , Norm (Norm $(A^{(2)},$ $H_{1}),$ $H$ ) $>$$=$$<H$ , Norm (Norm (Norm $(A^{(2)},$ $H_{1,3}),$$H_{1}$), $H$ )$>$は、 大きな wreath 積群となっていて、 これだけでは不十分$A^{(2)}$.
.

$=$が、 十分小さい群となって、 正規化群が簡単に計算できる[Remark]

5$H/A^{(2)}$Magma では、 Norm $(G, H)$ の計算は $H$$G$となることが必要。

部分直積群 (Subdirect Product).
.

$H$と $N=$ Norm $(G, H)$ が共通の orbit をもたない “簡単” な場合

上、 2 個の orbit $O,$ $O’$ をもつ。

$H$

は、$N$の作用は、 $O,$ $O’$ を交換する。

$\Rightarrow H$$K$である群に対して、 Norm $(A^{(2)}, H)$ を計算している。

$\Omega$の $O$ と$O’$上への作用 $(H, O),$ $(H, O’)$ は、 置換群として同型。

は $O$ 上の置換群、 $L$ を $O’$ 上の置換群、 直積群 $K$【定義】 (部分直積群) 部分群 $H$$L$

を $\Omega=O\cup O’$ 上の置換群とする。

で、 $K\cong(H, O),$ $L\cong(H, O’)$ が成立するとき、 $H$ を部分直積. ..
群という。 より多くの個数の直積の部分直積群も、 同様に定義する。
部分直積群の構成法 GAP システムのコマンド SubdirectProducts を使用する。
$K$

$L$

$K_{2}$$K_{1}$$K_{8}$$K$$\sigma=(21’$$K^{\sigma}$$42’$$3’1’$$4’5’$$65’$$36’)=(1’, 2’, 4’, 5’, 6’, 3’)$

SubdirectProducts では、 下の様に作用する群を構成するので、$O$

$O’$

$K$

$K$

70
一般の場合では、 共役に移す元$\sigma$を求める必要がある。

部分直積群の正規化群計算 ( $H$ が、 置換群として同型に作用する 2 個の orbit $O,$ $O’$ をもつ場合)

1. Action $(H, O)$ を Action $(H, O’)$ に移す共役元 を計算する。
昨年の本研究集会の共役計算法を利用【注意】 Action $(H, O)$ は可移となっている。
$\sigma$$arrow$2.

$\sigma$から、 $O$ と $O’$ を交換する元 $n\in N$ を構成する。

3. (a) 【方法 1 】正規化群中の$O$と $O’$ を交換しない部分群を$N_{O}$を計算する。

$arrow N=<n$ , $No>$ となる。

【注意】 $H$ と$N_{O}$は共通の orbit $O$ をもつ。

(b) 【方法 2 】 ActIon $(H, O)$ の $O$ 上の正規化群 $M$ を計算し、 Norm $(<n, M>, H)=N$ を計算する。
【注意】 $<n,$ $M>\cong Wreath$ Product $(M, Sym(2))$ が成立。
計算実験の様子から、【方法 1 】 は GAP 向き、【方法 2 】 は Magma 向き。

.
.
.
.

$H$の orbit の個数が 2 より多い場合についてorbit の個数が 4 まで、 計算実験をした。
方法 1 では、最大で、 4 個の orbit の置換全体 $4!=24$ 個の $n_{i}\in N$ を求め、各鱗によって orbit の置換を行った後、正規化群中のすべての orbit を固定する部分群$N_{0}$を計算して、 $N=<\cdots,$$N_{0}>$orbit の個数が多いとき、各 orbit は、 $|O_{j}|\ll|\Omega|$ となり、 Action $(H, O_{j})$ の正規化群計算は簡単。 orbitの集合上への作用の計算が本質的部分と考えられる。
本実験では、$|O_{j}|$が比較的大きく、 Action $(H, O_{j})$ の正規化群計算と orbit 集合への作用の計算が混ざ計算実験

61$\cdots,$を求める。

ることによって、 計算困難を引き起す場合を想定。

6$n_{i},$

16 次の可移置換群 2 個の直積の正規化群計算 in $Sym(32)$

16 次の可移群 1954 個

TransitiveGroup 16, $i),$$($$(1$$i$

1954$)$Norm ( $Sym(32)$ , TransitiveGroup(16, ) の全計算時間
1632 秒 最新バ ジョン
GAP〃210 秒
GAP 本研究の方法
最新バージョンは、?
Magma2.8
72 秒 5th Nov 2011 Magma V2.17-13
Magma28 本研究の方法$i)^{2}$ー【参考】 16 次の可移置換群の正規化群計算 in $Sym(16)$Norm ( $Sym(16)$ ,TransitiveGroup(16, ) の全計算時間
253 秒 最新パージョン
GAP$i)$$GAP+$ 可移群への工夫

165 秒

Magma2.8
Magma2.17-1249 秒
17 秒〃

by Magma calculator

71
16 の可移置換群 2 個の直積の正規化群計算 in $Sym(32)$ の例$\frac{Norm(Sym(32),Transit\dot{I}veGroup(16,i)TransitiveGroup(16,j))\text{の計算時間}}{ijMagma2.8Magmaca1cu1atorGA}$

1484
1379

1484
1379

1223

1223
1187
465
1075
1505
1502
1501
1210
1210
1187

1187
465
1075
1505
1502
1501
1221
1461
1223
1075
1502
1484

6.2

1501

1505
1501

PrimitiveGroup 8,$($$3)^{4}$5793 秒$>60$ 秒

0.3 秒

11043 秒$>60$ 秒

0.3 秒

10199 秒$>60$ 秒

0.3 秒

5847 秒$>60$ 秒

0.4 秒

145 秒

$>60$ 秒

0.2 秒

13 秒

29 秒
02 秒

780 秒

08 秒

493 秒

362 秒

125 秒

466 秒

436 秒

223 秒

321 秒

$>60$ 秒

61 秒

0.4 秒
0.2 秒
0.2 秒
1140 秒

28 秒

12 秒

585 秒

6035 秒$>60$ 秒

398 秒

27438 秒13805 秒24135 秒
140 秒$>60$ 秒$>60$ 秒の部分直積群の正規化群計算 in $Sym(32)$

4 個の PrimitiveGroup(8, 3) の部分直積群の同型類 56 個

Norm ( $Sym(32)$ , PrimitiveGroup(8,の部分直積群) の計算時間 (秒)番号$Magma2.8/$ calculator
GAP 本研究 GAP 本研究 Magma
全計算
1,083
11,595
227,761
296
$>60$
14
11
186
9422
2.9
$>60$
2,058
48
372
4.6
187
$>60$
4,406
49
1293
3.0
487
50
13116
54
3798
5.0
$>60$
2,58454
2018
3.2
273
15
0.6
11.04.3
4.3
43945
176.0
2.0
2.2
0.790151
198.1
4.3
4.4
0.453017
220.02
0.3
0.15
0.1
19.6
4278
3.1
31.215.228.7$3)^{4}$

6.3

PrimitiveGroup 8,$($$1)^{4}$の部分直積群の正規化群計算 in $Sym(32)$

4 個の PrimitiveGroup(8, 1) の部分直積群の同型類 49 個

72Norm ( $Sym(32)$ , PrimitiveGroup(8, の部分直積群) の全計算時間
195 秒 最後の 1 個:180 秒，残り 15 秒
GAP
$24=4!$ 倍 (orbit 4 個)
264 秒
GAP 本研究の方法$1)^{4}$$\approx 15$

Magma2.8
Magma28 本研究の方法.

6610 秒
13 秒

GAP ライブラリの PrimitiveGroup について.

PrimitiveGroup $(8,1)\cong AGL(1,8)$$PrimitiveGroup(8,3)\cong AGL(3,2)$【補足】

Magma は 20111210 にでた version 218 で、 置換群の正規化群計算と部分群の共役計算が、飛躍的に改善された。本研究の Magma Calculator で 1 分以上かかっていた場合は、 すべて、 瞬時に計算できるようになった。 そこで、 PrimitiveGroup 16, $11)\cong AGL(4,2)$ を 4 個使った部分直積群を使った実験をしてみると、$($

本実験のときと同様 1 分以上場合がでてきた。
GAP は、 4.5 の version が出ている。 これには、本研究で考えている群の対称群内における正規化群計算
では、 本研究の Magma 向けの方法が組込まれている。