数理解析研究所講究録
第 1666 巻 2009 年 127-134

127

同じアソシエーションスキームを作る群の計算
宮本泉*
IZUMI MIYAMOTO

山梨大学
UNIVERSITY OF YAMANASHI

1Introduction
可移な置換群は、 自己同型群が可移なアソシエーションスキームを作る。 このようなアソシエーションス

キーム 1 ま schurian であると呼ばれている。 schurian なアソシエーションスキームは、 その自己同型群からばかりでなく、通常、複数の可移な置換群からも同じものが得られる。本講演では、 schurian なアソシエーションスキームから、 それを作る可移な置換群のすべてを計算することを考える。 31 次までの可移な置換群は分類されている [5] ので、 これを使えば、 どの可移な群がどのアソシエーションスキームを作るかは分る。 アソシエーションスキームの分類は、 32 次 [4] でもできているので、 もし、 それが計算可能な範囲内であれば、 32 次の可移な置換群のすべてを作ることができることになる。

以上のような考えで計算を始めたが、 本発表の後、 2009 年 1 月に 32 次の可移置換群の分類結果 [1] が発表された。 その結果によると、 約 280 万個の群が存在するということである。 本実験では、 その時点で約30 万個の群が得られていて、 群から作られる 4000 個ほどのアソシエーションスキームのうち残っているのは 150 個ほどであったので、 これらのアソシエーションスキームから 250 万個の群が出てくるということになる。
したがって、 本発表の意義は薄れてしまった。 しかし、 可移置換群の分類では、 今までの経緯から、 なんらかの再検証は必要であることは明白となっている。 また、 いずれの文献 [5, 1] でも、 分類をする具体的なGAP システム 2に必要な関数はほとんどそろっていることを示し、 本発表のもう 1 つの目的であった GAP の関数の使い方コンピュ – タプログラムは示されていない。 そこで、 ここでは、 数式処理ソフトウェア$[$の紹介を中心に、 具体的な説明を行うことにする。

GAP

2$1_{-}^{-}$

よる置換群の基本的な計算

gap $>G;=Group^{(}$ [ (1 , 2,7, 5, 10, 11) (3,9,6) (4,8),$gap>$

IsPermGroup (G) ;$\#G$(1,2, 12) (3,7, 11) (4, 5,6) (8,9, 10)]は置換群 ?

true
MovedPo nt $s(G)$ ; $\#G$ の動かす点集合[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]$gap>$$i$

Orbit $(G, 1)$ ;#点 1 と の作用で移りあう点集合[1, 11, 12, 10, 7, 2, 5, 9, 3, 4, 8, 6]$gap>$

Hmiyamoto@yamanashi.ac.jp$G$$)$; ;$]$

128

Orbits (G);$gap>$$\#G$

で互いに移りあう点の集合の全体

12, 5, 11, 10, 6, 3, 8, 4, 9 1 1
IsTransitive $(G, [1. . 12])$ ; #可移 Orbits $=[MovedPoints])7$[ 1, 2, 7,$[$$gap>$$($truegap
gap

$>$

Gl: Stabilizer (G. 1); ; #点 1 の固定部分群$>$

Orbits (Gl);$=$[ [2, 6, 12, 8, 11,

gap
$f$

3 ], [4, 7, 101, [5, 9]]

IsTransitive (Gl, [1. . 12]);

$>$

alse

gap

$>$

Orbit ( $G,$ $[1,5]$ , OnSets); #点集合の点ごとに作用[ [1,5 ], [2, 10 ], [2, 6 ], [7, 11 ], [8, 12 ], [3, 7 ], [4, 12 ], [3, 11 ],[1, 9], [5, 9], [6, 10], [4, 8]$]$

Orbit ( $G,$ $[1,5]$ , OnTuples); #点対に作用$[[$ 1, $51,$ $[2,10],$ $[2,61,$ $[7,11],$ $[12,8],$ $[7,31,$ $[12,4],$ $[5,1]$ ,$gap>$[11, 3 ], [1, 9 ], [5, 9 ], [11, 7 ], [10, 2 ], [6, 2 ], [3, 7 ], [10, 6],

6, $101,$ $[3,111,$ $[8,12],$ $[4,12],$$[$

3$[9,5],$ $[8,41,$ $[4,81,$ $[9,11 ]$置換群の作るアソシエーションスキーム
定義 (アソシエーションスキーム)$\{R_{k}\}_{k=1,2,\cdots,d}$ASl.

が点集合 1, 2,$\{$$\{R_{t}\}_{t=1,2,\cdots,d}$$\cdots,$

は、

$\{$

$n\}$

1, 2,

上のアソシエーションスキームであるとは、$\cdots,$$n\}\cross\{1,2, \cdots, n\}$の分割

AS2. $R_{1}=\{(1,1), (2,2), \cdots, (n, n)\}$AS3. $R_{t}\cdot=\{(j, i)|(i,j)\in R_{t}\}$AS4. どの $(i, k)\in R_{u}$ に対しても、次の点の個数 $Pstu=\#\{j|(i,j)\in R_{s}, (j, k)\in R_{t}\}$ は一定
Transitive な置換群の点対 $\{[i,j]\}$ 上の orbit 全体をとするとアソシエーションスキームと,,なる。 orbit ごとに番号 を付けて、 それを成分とする行列で表すと下のようになる。
[例] 下の 6 点上の置換群 で、 点対 $\{[i,j]\}$ 上の orbit が 4 個のとき、 $t=0,1,2,3$ として、
$R_{0},$$R_{1}$$\cdot\cdot\cdot$$R_{d}$$t$$G$

gap $>G:=Wre$ at $hPro$ du ct Group $((1,2,3))$ , Gr oup $((1,2)))^{-}(1,2)$ ;$($Group $([(1,3,2),$ $(4,5,6)$ , (1, 5) (2, 4) (3, 6) ]$)$Orbits ( , Tuples ([1. . 6], 2) , OnTuples);$[[[$ 1, 1 1, [3, 3 1, [5, 5 ], [2, 2 1, [6, 6 ], [4, 4]],

gap

$>$

$G$

$[[$ 1, 2 1,$[$[[1, 3],$[[$ 1, 41,

3, 1 1,[5, 41,[2, 3 1,[6, 5 ],

[4, 6]].

[3, 2],$[$

5, 6 1,[2, 1],[6, 4],[4, 5][3, 4],$[$

1, 51,[5, 2],[2, 4],[3, 5],[1, 6],[5, 1],[2, 5],[4, 2],[2, 6],[4, 1],[6, 3 1,[4, 3][3, 6],

1 ]$]_{*}$[6, 2[6. 1 ],

1,

[5, 3],

129$A=(333201$$333201$$333021$$203331$$023331$$023331)$

4Transitive な群の性質$gap>$AllBlocks (G); #MovedPoints の分割を与えるのが block[1, 5, 9 ] ][[1, 4, 7, 10],$gap>$

Orbit $(G,$ $[1,4,7,10]$ , OnSets ; #その分割$)$10 ], [2, 5, 8, 11 ], [3, 6, 9,$gap>$ IsPrimitive (G);は原始的 (block 無し) ?
[ [1, 4, 7,121 ]

$\#G$

$f$

alse

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

primitive な置換群

2499 点まで (primitivetransitive な置換群

30 点まで$\Leftrightarrow 1$

点の固定部分群が極大)

アソシエーションスキームの分類 [4] は、 30 点までと 32 点、 33 点、 34 点、 38 点で、 できている。
それぞれの個数Transitive な置換群の分類は、 30 次までは、 AHulpke[5] 他によりなされている。 31 次は素数次なので、 可移な群は primitive になる。 32 次 ま、 J. J. Cannon と D. F. Holt[1] による。 それらに書かれている分類
$*|$

130

方法の概要は、 以下の通りである。
群は、 imprimitive なもののみを考えれば良い。 $G$ に、サイズ$p$の block があると、 Symk $=$SymmetricGroup $(k)$とおいて、$G\subseteq$

WreathProduct $(Sym_{1}, Sym_{n/\ell})$となることが知られている [3]。これにしたがって、 次数の小さな transitive group から順に分類していく。

対称群から、 次々と極大部分群を計算するには、 GAP の関数

ConiugacyClassesMaximalSubgroups $(G)$ 極大部分群の共役類
MaximalSubgroupClassReps $(G)$ その代表元が、 利用できる。 アソシエーションスキームの自己同型群にこの関数のみを適用して、 同じアソシエーションスキームを作る群を計算した結果、 11 次まではすべて計算できた。 最初に計算困難だったのは、 12 次で、2 個の 6 次対称群の WreathProduct となる場合で、 1 時間程度かかった。
群 $G$ において、 すべての block を固定するような部分群は、 $G$ の 1 つの block への作用の群の直積ばかりではなく、 関数 SubdirectProducts で得られる群のどれかになっている。 ここで、 すべての block を固定するような部分群の 1 つの block への作用と $G$ の 1 つの block への (その集合としての固定群の) 作用の違いについて考慮する必要があることを注意しておく。

gap

Sym: $=f$ unct ion (k) return Symmetri cGroup (k) ; end;
function ( k) . . . end
gap $>G;=WreathProduct$ (Sym (4), Sym (3)) ;$>$$<permutation$ group of size 82944 with 8 generators

gap$>$(1$*$$>$2 3 4) $arrow 3*(1*2*3)$ ;$*$$*$

82944

gap $>0:=0rbit$ ($[$$G,$ $[1$

[1, 2, 3, 4 1,. $.4]$ , OnSets);[5, 6, 7, 8 ],1 ]10, 11, 12[9,, OnSets); ;gap hom $;=ActionHomomorphism$ (gap $>D:=Dire$ ctProduct (Sym (4), Sym (4), Sym (4)) ; ;gap Image $(hom)=Sym(3)$ ; Kernel $(hom)=D$ ;$>$$G,$ $0$$>$

true

true

gap$>$

SD2: $=Subdire$ ctProducts (Sym (4), Sym (4)) ;[Group ( $[(1,2,3,4)(5,6,7,S),$ $(1,2)(5,6)$ 1),.

.

$(5,6)_{*}(6_{*}7).$ $(5,7,8)$ ] ,$(1.3,4)$Group $([(1_{*}2),$ $(1,3)$
Group $([(1,2)(3,4),$ $(1,4)(2,3),$ $(1,2,3),$ $(5,6)(7,S)$ ,(5, 6, 7).

(5, 7) (6, 8),Group$([$(1.2) (3.4),(3.4) (7, 8),

gap

$)$

(3, 4) (7.8)(1, 4) (2, 3) ,$\cdot$(2.4.3) (6.8.7)

$])$

,

(5, 6) (7.8).
$])$

$]$

.

(5.7) (6, 8),

SD3: $=List$ SD2, $u->SubdirectProducts$ ( Sym (4)) ; ;$gap>$ time;(ミリ秒。 SD4. SD5 と作っていくと、 非常に時間がかかるようになる。 )$>$$($$u$$)$

9145

gap

List (SD3, Length) ;[4, 8, 7, 6]#全部で 25 個

gap
gap

$>$

$>$

$>$

SD3 $:=Conc$ at enat on (SD3) ; ;List $(SD3,u->PositionProperty(SD3,v->IsConjugate(G,u.v)))$ ;
$i$

131

[ 1, 2, 3, 4, 2, 6, 7, 8, 7,10, 8, 2, 3, 7, 15, 16, 16, 18, 3, 4, 8, 16, 23, 4, 25](共役なものは、 そのうちの 1 つだけを考えれば良い)

gap

$>$

Set (last) ;[1, 2, 3, 4, 6, 7, 8,10, 15, 16, 18, 23, 25 1

$gap>$ List $(SD3\{last\},u->Is$ Subgroup $(D,u))$ ;ちょっと確認[true, true, true, true, true, true, true, true, true, true, true, true, true ](注) 上の共役をとる計算は、 $G$ で行うのではなく、 以下に出てくる MaximalSubgroup ごとに行わなければならない。
この中から、 Normalizer(正規化群) が transitive なものを選ぶ。
同じことを、 Sym4 の primitive 部分群と $Sym_{3}$ の transitive 部分群に対して行う必要がある。

Image $(hom)$ の部分群と Kernel $(hom)$ の SD3 の群との結び付け方

5gap

$>$

MAX$:={\rm Max}$

imal Subgr oupCl as Reps (Image (hom)) ;$s$[Group ( $[(1,2,3)$ ]), Group $([(2,3)$ ]) ]

gap

$>$

List (MAX, $u->$ IsTransitive ( , MovedPoints (Image $(hom)$ )));
$u$[true,gap

$>$

$f$

alse]

MAX: Filtered (MAX, $u->$ IsTransitive ( , MovedPoints (Image $(hom)$ )));
$=$

$u$

[Group ( $[(1,2,3)$ ]) ](繰返し行って、 Image $(hom)$ の可移部分群のすべてを求める)$gap>$[$<$

MAX: $=List$ (MAX, $u->$ PreImage (hom$>$$>$]

MAX: Concatenat ion ([G] , MAX) ; ;$G$も含めて、 次の処理へ)

NSD3: $=List$ MAX, $v->List$ (SD3, $u->Normalizer(v,u)$ ) ; ;List NSD3, $u->List(u.v->IsTransitive(v,$ $[1$ . . $12])))$ ;$($$)$$($[true, false, false, false, .
[true, false, .

gap$>$の中への引戻し)$G$$=$(最初に与えた群$[$));(permutation group with 11 generators$gap>$

gap
gap

$u$

. 中略. .true, false, true],

中略. . true, false, true]$]$

NSD3: $=List$ (NSD3, $u->Filtered$ (TransPosedMat ( $[u$ , SD3]), $v->IsTransitive(v[1],$ $[1$ . . $12])$ )); ;で))$gap>$ NSD3 [1] [3] ; (SubdirectProduct とその正規化群の組 (逆$>$$||\ovalbox{\tt\small REJECT}$$[<permutation$ group of size 82944 with 14 generators ,permutation group of size 6912 with 11 generators ]gap List (NSD3, $u->List$ ( $u,v->IsTr$ ansitive $(v[1],$ $[1$ . . $12])$ ));
$>$

$<$

$>$

$>$

[ [true, true, true, true, true, true, true] ,[true, true, true, true, true, true, true]gap$>$$]$(確認)

List ([1. . Length (MAX)], $u->List$ (NSD3 $[u],$ $v->$ Image ( $hom$ , $v[1])=$ Image $(hom$ , MAX $[u]))$ ) ;[ [true, true, true, true, true, true, true],[true, true, true, true, true, true, true]

gap
$>$

$>$$]$(確認 OK)

List ([1. . Length (MAX)], $u->List$ (NSD3 $[u],v->$
PositionProperty (NSD3 $[u].w->$ IsConjugate (MAX $[u],v[2],w[2]$ )) $))$ ;$[[1,2,3,4,5,6,7]*[1,2,3,4,5.6,7]]$ (確認OK)

132
gap $>Y;=NSD3[1][3]$ ; ;gap nhom: NaturalHomomorphiSmByNormaiSubgroup $(Y[1],Y[2])$ ;
$>$

$=$

[$(6,8)(9,10)$ , 中略[$<$identity$>$of...,$f$$<$

identity$>$of$->$. . . , 中略 $f2^{-}2*f3$ ]SubdirectProduct の群 $Y[2]$ を結びつる。
Intersection ( $Y[1]$ Kernel $(hom)$ ) $=Y[2]$ ;: Kernal $(hom)=D)$$Y[1]$ の $hom_{-}\vee$ よる像と

gap

(1, 5, 10, 4, 7, 9, 3, 8, 12, 2, 6, 11) ]

$>$

alse.

$(\grave{\{}f$

しかし、 $Y[1]$ のままでは直接結びっいていないので、 補群を計算(現時点では、 正規部分群が solvable の場合のみ動くアルゴリズム)

gap

Complementclasses (Image (nhom), Image (nhom, Intersection $(Y[1],D))$ );$>$[ $<pc$group with 2 generators $>,<pc$ group with 2 generators ]$gap>$

compl: $=List$ last, $u->PreImage$ (nhom, ) $);$ ([$>$$($$u$permutation group with 13 generators ,$<$$>$$<$$G$中への引戻し)

permutation group with 13 generators$>$]最終確認

gap $>Lis\dot{t}$ compl, $u->IsTransitive(u,$ $[1$ . $.12]))$ ;$($[true, true ]gap

IsConjugate (SymmetricGroup (12), compl [1], compl [2]);

$>$

false

gap

List (compl, TransitiveIdentification);$>$[290, 291]

gap

List ([1, 2]. $u->RepresentativeAction$ (SyretricGroup (12),$>$

TransitiveGroup (12, last $[u]$ ), compl $[u]))$ ;$>$[(2, 5, 6, 10, 4) (3.9, 11, 8, 7),gap(2.5, 6, 10, 4) (3, 9, 11, 8, 7) ]List ( $[1_{*}2],u->TransitiveGroup$ (12, last2 $[u]$ ) last $[u]=compl[u]$ ) ;[true, true 1$>$

6

SubdirectProduct を使わない方法 (Kernel が可解な場合)
少しの例外を除いて、 極小正規部分群は elementary abelian となる。 本実験では、 SubdirectPriduct の場

合は後に廻して、 下に示す elementary abelian group に作用したときの不変部分群を計算する関数を利用した。 文献 [5] にはこの方法への言及は無いが、 文献 [1] では、 16 次の極小可移置換群の不変にする位数のelementary abelian2-group の部分群をあらかじめ求めた後に、 その正規化群を利用して計算を行っている。

gap

$>$

Gl: $=Stabilizer$ ( $G,$ $0[1]$ , OnSets);$<permutation$ group of size 27648 with 13 generatorsgap$[$$2^{16}$$>$().

$>$

Kl: $=List$ (GeneratorsOfGroup (Gl), $u->RestrictedPerm(u,0[1])$ );. . . , $0,$ $(3,4)$ , (2, 4, 3), (1, 3) (2, 4), (1, 4) (2, 3)$]$

gap $>K1:=Group(K1)$ ;Group $([$ (), . . . (3, 4), (2.4, 3), (1 , 3) (2, 4). (1, 4) (2, 3) ]gap EAS: $=ElementaryAbelianSeries$ (Kl);$>$$)$

133[Group $([(3,4),$ $(2,3,4),$ $(1,3)(2,4)$ , (1, 4) (2, 3) ] ,$)$Group $([(2,3,4),$ $(1,3)(2,4),$ $(1,4)(2,3)$ ] ,Group $([(1,3)(2,4),$ $(1,4)(2,3)$ ] , Group $(())$$)$$)$

gap
gap
gap

$>$$>$$>$$]$

EAS: $=List$ EAS , $u->NormalClosure(G,u))$ ; ;$($EAS: $=List$ EAS, $u->Intersection(u,D))$ ; ;MAXI: $=MAX[1]$ ;$($$<permutation$ group of size 82944 with 8 generators

gap[$>$$>$

hom2 $:=Nat$ uralHomomorphi smByNormalSubgroup (MAX 1, EAS [2]) ;. . . 中略. . . , (1, 5) (2, 6) (3.7) (4, 8) ]$(1,2,3,4)$ , (1, 2),$->$$[ f5, f5, f4, f4, f3, f3, f2, fi*f2 ]$
gap

$>$

conj $:=List$ (GeneratorsOfGroup (MAXI), $u->$

ConjugatorIsomorphism (Image (hom2 , EAS [1]), Image (hom2, $u)$ ) ;$>$$)$$[ - f5, \wedge f5, - f4, \wedge f4, - f3, \wedge f3, \wedge f2, -fi*f2]$

gap

INVS $:=I$ nvar ant Subgr oups Element aryAbel $imGr$ oup (Image (hom2, EAS [1]), onj) ;[Group $([$ ] , Group $([f3*f4*f5 ])$ , GrouP $([f3*f5, f4*f5])$ , Group $([f3, f4, f51) ]$$>$$i$$c$$)$

gap

$>$

[permutation group with 9 generators $>,$ . . 中略$<$

INVS: $=List$ INVS, $u->PreImage$ (hom2,$($...
gap$>$$<$’$u$);$)$

permutation group with 12 generators..
]$>$

nhoms: $=List$ (INVS, $u->$

NaturalHomomorphiSmByNormaiSubgroup (Image (hom2),$>$[IdentityMapping$($Group ([fi, $f2,$ $f3,$ $f4,$ $f5]$ )$)$$u$)$)$;,$[fl, f2, f3, f4, f5 ]$$[fi, f2, f3*f4, f3, f4]$ ,$[fl, f2, f3, f4, f5 ]->$ $[fi, f2. f3, f3, f3]$ ,$[ fl, f2, f3, f4, f5]->$ [fl, . 中略. identity of. . .]
$->$

$<$

gap
$[$$>$[

group with 2 generators ,$>$

[Group(gap$[$fl,$f2$,. . 中略. . ,$<$

group with 2 generators$<pc$identity$>$of...

$]$)]$>$],. . . 中略. . .

$]$compls: $=List$ (nhoms, $u->List$ (Complementclasses (Image (u) , Image ( , Image (hom2, EAS [1])) , $w->Pre$ Image $(u,w)))$ ;$>$$[$$]$

compls $:=Li$ st (nhoms, $u->$ ComPlement clas ses (Image (u), Image $(u$ , Image (hom2, EAS [1])))) ;$<pc$$>$$>$$)$$u$[$<pc$

group with 2 generators[Group ([f3,gap$>$$f5$$<pc$, fl, $f2]$ ) ]group with 2 generators$>$],. . . 中略. . .

$]$List (last, $u->List$ ( $u,v->$ IsSubgroup (Image (hom2), $v$ )));[ [true, true],$gap>$$f4,$$>,$[true ],

[true, true],[true] ]compls: $=List$ (nhoms, $u->List$ (Complementclasses (Image (u), Image ( , Image (hom2, EAS [1])) , $w->Pre{\rm Im}$ age (hom2, Pre Image $(u,w)$ ) $))$ ;$>$$)$$u$group with 11 generators$<permutation$ group with 11 generators[ $<permutation$ group with 12 generators ],[ $<permutation$ group with 13 generators ,permutation group with 13 generators[ $<permutation$ group with 14 generators][ [ $<permutation$$>,$$>$],$>$],$>$$>$$>$$<$$]$(確認作業)

gap
gap

$>$

$>$

complsc: $=Concatenation$ (compls); ;List (complsc, $u->PositionProperty$ (complsc, $v->IsConjugate(G,u.v)$ ));134[ 1,2, 3, 4, 5, 6 1

gap

List (complsc, TransitiveIdentification);$>$[275, 276, 283, 290, 291,72941

アソシエーションスキームの利用
すべての transitive group を生成するには大ざっぱなので、 出来上がった分類のすべての群の Maximal-Subgroup を計算して確認 (AHulpke[5]) している。 本実験では、 1 つのアソシエーションスキームを作る群毎に分類する。 アソシエーションスキームの自己同型群から始めて、 その部分群で同じアソシエーションスキームを作るものを計算して行く。 アソシエーションスキームの自己同型群 $G$ が transitive なとき、 $G$のtransitive な部分群 $H$ で、$G$と $H$ の 1 点固定部分群が一致するものが同じアソシエーションスキームを構成する。

SubdirectProduct を使う場合を、 まだ、 取り扱っていないが、 残りの部分についての大体の計算時間は、
22 次までは、 かかっても数時間、 24 次から 28 次は 1 日程度、 30 次のとき 3 日程度であった。 どの次数でも、 計算に長時間を要するのは、 ごく少数の場合で、 ほとんど全ての場合は、 短時間で計算できている。

GAP ライブラリの transitive な群を参照すると、 おおむねプログラムのバグは無くなって計算できていることがわかる。 しかし、 後まわしにして残っている場合が、 どの程度の困難さであるか、 予断はできない。

この方法で、 32 次の場合の検証をするための実験を続けていて、 メモリの使用量や計算に時間のかかる部分などを調べて、 改良を進めている。

参考文献[1] J. J. Cannon and D. F. Holt. The transitive permutation groups of degree 32. Experriment. Math.
17-3:307-314, 2008,[2] The GAP Groups. Gap-groups, algorithms and programming, version 4. Lehrstuhl $D$ fur Mathematik,
Rheinisch Westfalische Technische Hochschule, Aachen, Germany and School of Mathematical andComputational Sciences, Univ. St. Andrews, Scotland, 1997.

[3] M. Krasner, L. [A.] Kaloujnine. Produit complet des groupes de permutations et probl\‘eme d’extension
de groupes II. Acta Sci. Math. (Szeged), 1439-66, 1951.
[4] A. Hanaki, I. Miyamoto. http: $//kissme$ . shinshu-u. ac. $jp/$ as/[5] A.Hulpke. Constructing Transitive Permutation Groups. J. Symbolic Comput., 391-30, 2005.