数理解析研究所講究録
第 1815 巻 2012 年 100-105100

2 重可移群に共役で含まれる可移部分群の一計算方法
宮本泉*
IZUMI MIYAMOTO

山梨大学
UNIVERSITY OF YAMANASHI

1Introduction

1.1

群$G,$ $H$$G$に共役で含まれる部分群: 集合$\Omega$上の置換群のとき、ある $g\in Sym(\Omega)=\{1,2, \cdots, n\}$ で、 $H$ の -共役 $g^{-1}Hg=H^{g}$ が$g$

$H^{g}\subseteq G$となることはあるか？ また、 そのような1.2.
.

$g$の探し方は？

GAP システムの群のライブラリ

置換群のライブラリには、30 次までの可移群
2499 次までの primitive な群がある。

群 $G$ と、 その部分群 $H$ が、 共に、 ライブラリにある群でも、 そのままでは、 $H\subset G$ となるとは限らない。
$arrow$

ライブラリは同型類の分類リストだから。

すなわち、 置換群のライブラリにあるのは、共役類 $\{G^{g}|g\in Sym(n)\}$ のうちの 1 つ。
そのとき、

*imiyamoto@yamanashi.ac.jp$H$が $G$ の部分群$\Leftrightarrow\exists g\in Sym(n)$such that$H^{g}\subset G$

101
1.3

【例 1 】散在型有限単純群 Co.3

Co.3 は、 同じく散在型有限単純群 $McL$ や $HS$ を極大部分群として含む。 Co.3 は、 276 次の 2 重可移置換群として与えられる。 このとき、 具体的に、

Mc.
.

$L,$$HS\subset$

Co. $3\subset Sym(276)$となるように、 $McL$ や $HS$ を求める方法は？
$McL$ は、Co.3 の 1 点固定部分群となる。 $arrow$ 包含関係がよく分かる。

は、 100 次と 176 次の 2 通りの置換群として与えられる。 これから、 276 次の置換群として作るこ$HS$とができるが$([$例 $2])$、このようにしてできた $HS$ は、 そのままでは $HS\subset Co.3$ とはなってくれない。

Case 1: この作り方が適当であった場合。 ある $g\in Sym(276)$ によって、 次が成立。

$-$$HS^{g}\subset$

Co.3

Case 2: この作り方が適当でなかった場合。 すべての $g\in Sym(276)$ で、 次が成立。

$-$$HS^{g}\not\subset Co.3$.
.

1.4【例 2 】 $HS$$HS$が 100 次の置換群として与えられたとき、 1 点固定部分群は、$HS$は 176 次の 2 重可移群となる。 $M(11)$ も、 176 次の primitive な群となる。 このとき、 次を満たす$M$(ll) である。

$g\in Sym(176)$ を求めることができるか？
$M(11)^{g}\subset HS$

GAP システムの primitive な群のライブラリから、 176 次の群として $M(11)$ と $HS$ をもってきて、 上の条件を満たす$g$を求めたい。

【注】 $M(11)$ は小さい群なので、 176 次の $HS$ の中で、 比較的簡単に生成させることができる。

.
.
.
.
.

1.5

問題の設定
例にあげたような有限単純群とその (極大) 部分群の包含関係を、 コンピュータで確認したい。
$H^{g}\subset G$を満たす$g$を探す一般的な方法は無い。

$H$が小さい群ならば、 $G$ の中に $H$ と同型な群を構成する方が易しいであろう。

$H$は、 比較的大きな群の場合を考えることにする。

$G$は $Sym(n)$ よりはるかに小さいので、 $H$ と $g\in Sym(n)$ で $G$ を生成するような$g$を探すのは無理。

102
2

準備2.1

今までの研究との関連群の可移拡大 $n-1$ 次の可移な群 $H$ から、$n$

次の 2 重可移群 $G$ で、 1 点固定部分群が、$G_{n}=\{g\in G|n^{g}=n\in\Omega\}=H$となる群を構成する。
$arrow$

2.2

今回の実験

:

$G$

$H$

スーパースキームを使った構成法を得た (2006):

次の 2 重可移群、 3 重可移ではない。
次の可移群

$n$

$n$

$arrow H^{g}\subseteq G$となる $g\in Sym(n)$ を探す【注】可移拡大の $H$ も、 $H\subset Sym(n)$ で、 特に、 $n^{h}=n$ for.
.

2.3

$G,$

$H$

$\forall h\in H$の制約の主な理由$H$: プログラムが複雑にならないようにするため。

$c$: 必要となるスーパースキーム計算で、 爆発が起こらないようにするため。 スーパー スキームで群が決まるようにするため。

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

2.4への作用 : $(x, y)^{g}=(x^{g}, y^{g})$このとき、 下の作用の作る orbit の全体は、 それぞれ、
$G$.
.
.

は$\Omega$$G$上の置換群は可移、$\Omega^{2}$$\Omega,$$\Omega^{2}$$\Omega^{2}=\Omega\cross\Omega$

への作用

への作用
$\Omega^{2},$$\Omega^{3}$への作用$arrow$

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

コヒアラントコンフイギュレーション$arrow$

3-スーパースキームを作る。

2.5

スーパースキーム

定義．

$(\Omega, \Pi)$Sl.

がかスーパースキームであるとは、$\Pi=\{\Pi^{1}, \Pi^{2}, \cdots, \Pi^{t}\},$ $t\geq 2$, で$\Pi^{\ell}$$\Leftrightarrow$

は $1\leq\ell\leq t$ において$\Omega^{\ell}$の分割，

S2. $\sigma\in Sym(\ell)$ について，$\sigma((y_{1},y_{2},\cdots,y\ell))=(y_{\sigma(1)}, y_{\sigma(2)}, \cdots, y_{\sigma(\ell)}),$ $\Pi^{\ell}=\{R_{0}^{\ell}, R_{1}^{p}, \cdots, R_{d_{l}}^{\ell}\},$とおくと，すべての$R_{k}^{\ell}$と $\sigma\in Sym(\ell)$ , に対して、$\sigma(R_{k}^{\ell})\in\Pi^{\ell}$. . (symmetrec)$1\leq\ell\leq t,$

103
S3. projection$\pi_{j}^{\ell}$:$\Omega^{\ell}arrow\Omega^{\ell-1}$を$\pi_{j}^{\ell}((y_{1}, y_{2}, \cdots, y\ell))=(y_{1}, y_{2}, \cdots, y_{j-1}, yJ+1, \cdots, y_{\ell})$

すべてのS4. すべての

$R_{k}^{l}\in\Pi^{\ell},$$R_{k}^{\ell},$$2\leq\ell\leq t$$|(\pi_{j}^{\ell})^{-1}(y)\cap R_{k}^{\ell}|$3$2\leq\ell\leq t$で定義すると，に対して，$\pi_{j}^{\ell}(R_{k}^{\ell})\in\Pi^{\ell-1},$, と，すべての$y=(y_{1}, y_{2}, \cdots, y_{\ell-1})\in\pi_{j}^{\ell}(R_{k}^{1})$が存在．特に，$p_{k,j}^{\ell}=|R_{k}^{\ell}|/|\pi_{j}^{\ell}(R_{k}^{\ell})|.$$\cdots$に対して，constant$p_{k,j}^{\ell}=$(regular)Algorithm

.
.

3.1

Algorithm (スーパースキーム)$G$と $H$ の作るスーパースキームを計算する。

$H$の作るスーパースキームのフユージョンスキームを計算して、$G$の作るスーパースキームと同型になりうるものを探す。

.
.
.

$-(\Omega, \Pi)$が $(\Omega, \Pi’)$ のフユージョンスキーム$\Leftrightarrow\Pi^{\prime\ell}$は$\Pi^{\ell}$の refinement

同型になりうるものが得られたら、 その自己同型群が $G$ と共役になるかどうか計算する。

3.2

Algorithm (orbit)
上の orbit$G$と $H$ の$H$の orbit を適当にまとめて、 $Sym(\Omega)$ の元で移して $G$ の orbit と一致する可能性のあるものを求$\Omega^{3}$$\Pi^{3}$と$\Pi^{J3}$を計算する。

める。
$o$

orbit 全体を不変に保つ群が、究集会)

3.3$G$と共役であるかどうか計算する。 (共役計算の困難な場合 :2009 本研

計算の困難ざについて・可移な群の作るアソシエーションスキームでも同様な方法が適用できるが、 非常に多くの群が同じアソシエーションスキームを作る場合がある。 (2008 本研究集会).

同様に、 非常に多くの群が$\Omega^{3}$

上に同じ orbit を持っ、 すなわち、 同じ 3- スーパースキームを作る場

合がある。

.
.
.

primitive な群なら、 アソシエーションスキームで、 ほぼ決まる。
$2$重可移群は対称群と同じアソシエーションを作るので、 3- スーパースキームを考える必要がある。

$3$

重可移群では、 4-スーパースキームが必要、 しかし、$\circ H$の$\Omega^{3}$$\Omega^{4}$は直接計算では大きすぎる。

上の orbit 数が少なくないと、 計算が爆発する。 (20 個以下？)

次数 $n=|\Omega|$ が大きくても、計算については、$\Omega^{3}$$\Omega^{3}$上の orbit 数が少なければ計算可能。 (スーパースキームの自己同型で行っているので、 大変。 )

104
4

実験

4.1

GAP の primitive な群のライブラリから 31 次 $-200$ 次$\circ$

いずれの実験例でも、 計算時間の大部分はスーパースキームを表す $n\cross n\cross n$ 次の 3 次元配列の直接計算にかかっている。

$oH$ の orbit 情報およびそれらを結合して $G$ の共役群の orbit 候補を作る計算、 スーパースキームの自.
4.2

己同型群計算は、 全部で数秒程度。 (orbit 候補計算が爆発しない例を選んでいる。 )スーパースキームの自己同型群計算と $G$ の共役計算は、 1, 2 秒以内、 または、 計算困難 (2009 本研究集会)。

GAP のライブラリの記号、 次の primitive な群、 その他の記号$n$$G=Prim\dot{\ovalbox{\tt\small REJECT}}tiveGroup(n, i) , H=PrimitiveGroup(n,j)$

$S$

4.3

実験結果

: 得られたスーパースキーム，$Aut(S)$ : その自己同型群

105
5

考察

5.1.
.

【例】 $G=M(9)=3^{2}:Q(8)$ ,:$(\Omega, \Pi)$$\Pi(3)$:$H=3^{2}:2$の作るスーパースキーム、の分割で、 $(i, j, k)\in P\in\Pi^{(3)},$$G$$\Omega^{3}$$\Rightarrow|\Pi^{(3)}|=7$、$i,$ $j,$ $k$

は互いに異なる

すべて同じサイズで区別が困難

192 個の答-48 個は $G$ と共役な群-144 個は PrimitiveGroup $(9, 4)=3^{2}:8$ と共役な群.
.
.

5.2

5.3.
.

$\circ$.

.

5.4.

【例】 $G=Prim\dot{\ovalbox{\tt\small REJECT}}tiveGroup(156,5)=PSL(4,5)$
PrimitiveGroup $(156, 7)=PGL(4,5)$ が得られる$2$

つの $PGL(4,5)$ 間の共役元計算は、 GAP の関数 RepresentativeAction では困難 285 分より大2009 本研究集会の方法で、 105 秒【例】 $G=PrimitiveGroup(255,2)=PSL(8,2)$
スーパースキーム構成の計算:1 秒以下スーパースキームを表す 3 次元配列の計算 :235 分、 $1252MB$
スーパースキームの自己同型群計算 :42 秒-MacBook-

CPU: 2.4 GHz

メモリ: 4 $GB$667 MHz DDR2 SDRAM

可移拡大計算のときは、 群 $H$ の作用を考慮して 3 次元配列の直接計算はしていない$G,$$H$の制約条件

最初の例、 276 次の 2 重可移群 $G=Co.3$ と可移ではない $H=HS$
この方法の一般化は、 フユージョンスキームの計算になる (複雑？)$(\Omega, \Pi)$.

Intel Core 2 Duoが$\Leftrightarrow$$(\Omega, \Pi’)$のフユージョンスキーム

各 で、 分割$i$$\Pi^{\prime i}$は分割$\Pi^{i}$の refinement

結局、 $G$ の中に $H$ と同型な群を作る、 または、 $H$ を含む $G$ と同型な群を作ることが本質？