部分直積群の正規化群計算の高速化について (数式処理 : その研究と目指すもの)

(1)

部分直積群の正規化群計算の高速化について

宮本泉

IZUMI MIYAMOTO

山梨大学

UNIVERSITY

OF YAMANASHI

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

$G,$ $H,$ $K$

:

_集合$\Omega$上の置換群とする。

.

$H$ _と $K$は $G$ _{において共役}$\Leftrightarrow g^{-1}Hg=K$for

some

$g\in G$

.

$H=K$ として、$g^{-1}Hg=K$ とする$g$ をすべて求める

$\Rightarrow H$_の$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

notoriouslydifficultproblems

even

in permutation groups ofsmall 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$for any $i\in\Omega$

.

$G$ _{における点}$i$ の固定部分群_{$\Leftrightarrow G_{i}=\{g\in G|i^{g}=i\}$}

.

$G$_の$\Omega^{2}$ 上への作用

:

$(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$

ズの_orbitいくつかの和集合

$N$ _{となることより、}$N$のorbit は、$H$_{の同じサイ}

$\Rightarrow H$ _$N$ $A$ $G$, $A$

:

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

(2)

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)\}$, $\Omega$ $\Omega$上のorbit

$R_{2}=\{(1,3), (1,4), (2,3), (2,4), \cdots, (6,1), (6,2)\}$, 4個 $R_{3}={}^{t}R_{2}=\{(3,1), (4,1), (3,2), \cdots, (1,6), (2,6)\}$ 1 2 3 4 5 6 $C=645321(_{2}^{1}3230$ $303221$ $033221$ $032231$ $033221$ $033221]n\in Narrow(_{3}^{1}0322$ $032231$ $032321$ $033221$ $033221$ $033221]$ コピアラントコンフィグレイションの自己同型 $(032321$ $033221$ $033221$ $330221$ $303221$ $323021)\cong(330221$ $033221$ $303221$ $033221$ $023321$ $033221)$ 自己同型群 $Aut(C)=Group((3,5,4,6), (1,6,2,5)(3,4))\supsetneq H$ $Aut(C)$ の$\Omega^{2}$ 上のorbitへの作用

:

_馬，

$R_{1}$, $R_{2}$ $\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$p$(28,1528), G$=$ SymmetricGroup(28)

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

{1}, {2},

$\{$3, 4,_$\cdots,$$28\}$

$\Rightarrow\{3,4, \cdots, 28\}$_は、$H_{1},$ $N_{1}$共通のorbit $\Rightarrow N=<H\iota,$$(N_{1})_{3}>$

正規化群計算$N_{1,3}=(N_{1})_{3}$は、$H$ における点1,3の固定部分群$H_{1,3}$ を正規化する。

$n^{-1}H_{1,3}n=H_{1,3}$,for all $n\in N_{1,3}$

(3)

$H,$ $H_{1},$ $H_{1,3}$の作るコピアラントコンフィグレイション $C,$ $C^{(1)},$ $C^{(2)}$ _{の自己同型群}_$A,$ $A^{(1)},$$A^{(2)}$ _を計算す

る。

$|A|$ $=$ $2^{14}14!$ $=$ 1428329123020800

$|A^{(1)}\cap A|$ $=$ $|A^{(1)}|$ $=$ $2^{13}13!$ $=$ 51011754393600

$|A^{(2)}\cap A^{(1)}\cap A|$ $=$ $|A^{(2)}|$ $=$ 196608

$N=N(G, H)$ $=$ $<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$) $>$

$A$_{は、大きな}wreath_{積群となっていて、これだけでは不十分}

$A^{(2)}$_が、

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

.

$H/A^{(2)}$ _{である群に対して、}_Norm$(A^{(2)}, H)$ _{を計算している。}

.

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

5 部分直積群

(Subdirect Product)

$H$ _と _$N=$

Norm

_{$(G, H)$}_が共通の_orbit _{をもたない} _“簡単”_な場合

.

$H$ _は、$\Omega$上、 2個の

orbit$O,$ $O’$ _をもつ。

.

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

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

$K$ は $O$_{上の置換群、}$L$ _を $O’$_{上の置換群、直積群}$K$ $L$ _を $\Omega=O\cup O’$_{上の置換群とする。}

【定義】 (部分直積群) 部分群$H$ $K$ $L$_で、_{$K\cong(H, O),$ $L\cong(H, O’)$} が成立するとき、$H$ _{を部分直積}

群という。より多くの個数の直積$K_{1}$ $K_{2}$

. ..

$K_{8}$ の部分直積群も、同様に定義する。部分直積群の構成法GAP システムのコマンドSubdirectProducts を使用する。 $K$ $\sigma=(21’$ $42’$ $3’1’$ $4’5’$ $65’$ $K^{\sigma}$ $36’)=(1’, 2’, 4’, 5’, 6’, 3’)$

SubdirectProducts

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

(4)

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

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

1. Action$(H, O)$ をAction$(H, O’)$ に移す共役元$\sigma$を計算する。

【注意】Action$(H, O)$ は可移となっている。 $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_{i},$$\cdots,$$N_{0}>$

を求める。

.

orbitの個数が多いとき、各orbit は、$|O_{j}|\ll|\Omega|$ となり、Action$(H, O_{j})$ の正規化群計算は簡単。orbit の集合上への作用の計算が本質的部分と考えられる。

.

本実験では、$|O_{j}|$ が比較的大きく、Action$(H, O_{j})$ の正規化群計算と orbit集合への作用の計算が混ざ

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

6 計算実験

61

16 次の可移置換群

2 個の直積の正規化群計算

in

$Sym(32)$

16 次の可移群 1954 個 TransitiveGroup$($16,$i),$ $(1$ $i$

1954

$)$

Norm($Sym(32)$, TransitiveGroup(16,$i)^{2}$)の全計算時間

GAP 1632 秒最新バージョン

GAP 本研究の方法 210 秒〃

Magma2.8 ? 最新バージョンは、

Magma28 本研究の方法 72秒 5thNov 2011 Magma V2.17-13

【参考】 16次の可移置換群の正規化群計算in $Sym(16)$

Norm($Sym(16)$,TransitiveGroup(16,$i)$)の全計算時間

GAP 253秒最新パージョン

$GAP+$可移群への工夫 165 秒〃

Magma2.8 49秒

(5)

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

1223

10199秒 $>60$_秒 0.3 秒 1187 1187 5847秒 $>60$秒 0.4秒 465 465 145秒 $>60$秒 0.2秒 1075 1075 13秒 29秒 780秒 1505 1505 08秒 02秒 493秒 1502 1502 362秒 125秒 466秒 1501 1501 436秒 223秒 321秒 1221 1210 27438秒 $>60$秒 0.4秒 1461 1210 13805 秒 $>60$秒 0.2 秒 1223 1187 24135 秒 $>60$秒 0.2 秒 1075 1501 140 秒 61 秒 1140 秒 1502

1505

28秒 12秒 585秒 1484 1501 6035秒 $>60$秒 398秒

6.2 PrimitiveGroup

$($

8,

$3)^{4}$

の部分直積群の正規化群計算

in

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

Norm($Sym(32)$, PrimitiveGroup(8,$3)^{4}$の部分直積群)の計算時間 (秒)

番号 $Magma2.8/$calculator GAP 本研究GAP 本研究Magma

全計算 11,595 227,761 296 1,083 14 186 $>60$ ₉₄₂₂ _2.9 ₁₁ 48 2,058 $>60$ 372 4.6 187 49 4,406 $>60$ 1293 3.0 487 50 116 54 3798

5.0

13 54 2,584 $>60$ 2018 3.2 273 15 11.0 4.3

43945

4.3 0.6 17 6.0 2.0 90151 2.2 0.7 19 8.1 4.3 53017 4.4 0.4 22 0.3 0.15 0.1 19.6 0.02 42 78 31.2 15.2 28.7 3.1

6.3 PrimitiveGroup

$($

8,

$1)^{4}$

の部分直積群の正規化群計算

in

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

(6)

Norm

($Sym(32)$

,

PrimitiveGroup(8,$1)^{4}$の部分直積群)の全計算時間

GAP

195秒最後の

1

個

:180

秒，残り

15

秒

GAP本研究の方法 264秒 $\approx 15$ $24=4!$倍(orbit 4 個)

Magma2.8 6610秒

Magma28本研究の方法 13秒

GAP

ライブラリの PrimitiveGroupについて

.

PrimitiveGroup

$(8,1)\cong AGL(1,8)$

.

$PrimitiveGroup(8,3)\cong AGL(3,2)$

【補足】

Magma

は20111210にでたversion218 で、置換群の正規化群計算と部分群の共役計算が、飛躍的に改善

された。本研究のMagmaCalculatorで 1 分以上かかっていた場合は、すべて、瞬時に計算できるように

なった。そこで、

PrimitiveGroup

$($16,$11)\cong AGL(4,2)$ を 4 個使った部分直積群を使った実験をしてみると、

本実験のときと同様 1 分以上場合がでてきた。

GAPは、4.5の version_{が出ている。}これには、本研究で考えている群の対称群内における正規化群計算

部分直積群の正規化群計算の高速化について (数式処理 : その研究と目指すもの)