数理解析研究所講究録
第 1652 巻 2009 年 155-161155

置換群の組合せ論的可移拡大からできるデザイン
泉

宮本IZUMI MIYAMOTO

山梨大学
UNIVERSITY OF YAMANASHI

1*

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

は集合 $X=\{1,2, \cdots, n\}$ に作用する置換群とする。 $G$ は可移とはすべてのとなる $g\in G$ が存在することである。 (すなわち、 $X$ 上の orbit の個数が 1 個)$(i,j)^{g}=(i^{g},j^{g})$ で定め、 $X\cross X$ を $G$ の orbit に分ける。
$G$$i,$$j\in X$$G$に対して、 $i^{g}=j$の $XxX$ への作用を

例 $:X=\{1,2,3,4,5,6,7,8\}$$X\cross X$$=$$R_{0}+R_{1}+R_{2}+R_{3}+R_{4}+R_{5}$$=$$[43402515$$42043515$$20345451$$34502451$$44055321$$44550231$$44553201$$44355201]$臓$)=$ $\{(1,1), (2,2), \cdots, (8,8)\},$ $R_{1}=\{(1,2), (2,1), (3,4), (4,3), \cdots, (7,8), (8,7)\}$ ,$R_{2}=\{(1,3), (3,2), (2,4), (4,1), \cdots , (6, 8), (8, 5)\}$,$\cdots$

このとき、 $G=$ Group $([(5,6)(7,8),$ $(1,3_{J}2_{1}4)(5_{t}8_{1}6,7)$ , (1,6,2,5)(3,8,4,7) ]$)$これらの orbit の組合せ論的性質が、 以下に示すアソシエーションスキームとなる。

集合 $X=\{v_{1}, v_{2}, \cdots,v_{n}\}$ とし、 関係 $R_{i}\subset XxX,$ $0\leq i\leq d$ とする。
定義 : $(X, \{R\}_{0\leq i\leq d})$ がアソシエーションスキーム
は $X\cross X$ の分割
1. &,
2. $R_{4}=\{(v,v)|v\in X\}$
$R_{1},$$\cdots,$$R_{d}$.

3. ${}^{t}R_{d}=\{(v_{\dot{t}},vj)|(vj,v_{i})\in R_{t}\}=R_{t}$ for some$i*$4. 任意の $(u, v)\in R_{k}$ に対して $\#\{w|(u, w)\in R, (w, v)\in R_{j}\}$ は一定. これを、$G$が $X$ 上 2 重可移とは、 すべての $(i_{1}, i_{2}),$ $i_{1}\neq i_{2},$$g\in G$ が存在することをいう。 このとき、 $G$’miyamotoOyamanashi. ac.jp$(j\iota,j_{2}),$$j\iota\neq j_{2}$$pi_{l}j,k$とする.

に対して $(i_{1}^{g}, i_{2}^{g})=(j\iota,j_{2})$ となる

は $X\cross X$ 上の orbit の個数は 2 個となり、 $G$ の作るアソシ

156
エーションスキームによる $X\cross X$ の分割は下の様になる。

$XxX=R_{0}+R_{1}=[01111111$$G$$01111111$$01111111$$01111111$$01111111$$01111111$$01111111$$01111111]$の作るアソシエーションスキームは対称群のの作るものと同じになる。 そこで、 対称群と対称群ではな

い 2 重可移群を区別するためには、 $X^{s}=XxXxX,$ $X^{4}=XxX\cross X\cross X,$$\cdots$

上の orbit も考える必要がある。 そのために、 スーパースキームを導入する。
定義 :$(X, \Pi_{1\leq l\leq t}^{l})$が t-superscheme であるとは、

1.
2. $\pi_{l}:X^{t}arrow X^{l-1}$$\Pi^{l}=\{R_{0}^{l}, R_{1}^{l}, \cdots,\#_{d_{1}}\}$

$\}$

3.

こ,$\sigma\in$は$X^{l}$の分割 $(1\leq l\leq t, t\geq 2)$$(u_{1}, u_{2}, \cdots, u_{t-1}, u\iota)arrow(u_{1}, u_{2}, \cdots, u_{l-1})$

とおくと,$\pi\iota(R_{k}^{l})\in\Pi^{l-1}$が成立. さら$\#\pi^{-1}((u_{1}, u_{2}, \cdots, u))\cap R_{k}^{l}=\{\begin{array}{l}p_{k}^{l} if (u_{1}, u_{2}, \cdots, u_{l-1})\in\pi_{l}(R_{k}^{l})(regular)0 if (u_{1}, u_{2}, \cdots, u_{l-1})\not\in\pi\iota(R_{k}^{l})\end{array}$

SymmetricGroup $(l)$ に対して,$\sigma(R_{k}^{l})\in\Pi^{1}$が成立する。

ただし $\sigma(\#_{k})=\{(u_{\sigma(1)}, u_{\sigma(2)}, \cdots,u_{\sigma(\iota)})|(u_{1},u_{2}, \cdots,u\iota)\in R_{k}\}$ (symmetric)

例: $X$ 上の置換群 $G$ の$X^{l}$

上 orbit $(1\leq l\leq t)$ は t-superscheme

例:アソシエーションスキームは次のような 3- スーパースキームとなっている。 アソシエーションスキームから自然に誘導される$\pi$: $X^{3}arrow X^{2},$$X^{\theta}$の分割 $R_{4,j,k}=\{(u,v,w)|(u,v)\in R_{k}, (u,w)\in R\iota, (w,v)\in R_{j}\}$ を考えると、$(u,v,w)arrow(u,v)$ とおくと、 $\#\pi^{-1}((u, v))\cap R_{i,j,k}=\{\begin{array}{ll}p_{i,j,k} if (u,v)\in R_{k} \text{となつて}0 if (u,v)\not\in R_{k}\end{array}$いる。

2

置換群の可移拡大への応用$G$の点 $n$ の固定部分群を $G_{n}=\{g\in G|n^{g}=n\}$ で表す。

点 $n$ の固定部分群が $G_{n}=H$ となる 2 重可移群

$G$$X\backslash \{n\}$上、 可移な置換群として $H$ を与えて、を構成する。 あるいは、 $G$ が存在しないことを示す。

$|G$を $X=\{1,2, \cdots,n\}$ 上の 2 重可移群とするとき、 点 $n$ を伽する部分群 $G_{n}$ から $G$ を復元する. これらのことを、群を使わずに、$G_{n}$の作るスーパースキームから $G$ が存在するならばそれによって作られるはずのスーパースキームを構成することによって行う ([5, 6])。

方法 :$G_{n}$

上の orbit を集めて, 可能な $G$ の 3-superscheme をの作る &sup sdl-eme の構成する. これを、 superscheme の性質をチェックすることによって行う。
$G_{n}$$\propto$$X^{3}$の $(X\backslash \{n\})^{(3)}=\{(i,j, k)|$ 相異なる $i,j,$ $k\in X\backslash \{n\}$上の orbit の個数が 64 以下程度で計算できた。 本研究の計算機による実験は、 GAP システムを使って行っている。 GAP システムのライブラリにある 2499 次までの prinitive な群で上の条件を満たすものについてスーパースキームを構成した結果を表 1 に示す
さらに、 superscheme ができても、可移拡大の群が存在しないことがある。 そのような例の応用として、 tデザインの構成を試みる [7]。
$[7|_{0}$157

orbit-like set と t-デザイン

3.
.
.

定義 : $(X, B)$ が $t-(v, k, \lambda)$ デザイン$\Leftrightarrow$$v=|X|$$B$

は、 $X$ の$X$のどの$t$$k$点部分集合の mul-ti-set.. $B$ に属する点部分集合も、 ちょうど$\lambda$

$k$

点部分集合

$b$をブロックという。

個のブロックに属する。

点部分集合ににより作用させる。 $G$ が $X$ の 点部分集合全に対して、 $\{x_{1},x_{2,}x\}^{g}=$体の上に可移、つまり、任意の 点部分集合 $\{x_{1},x_{2}, \cdots, x_{l}\}$ ととなる $g\in G$ が存在するとき、 t-homogeneous という。 このとき、 $G$ の $X$ の 点部分集合上の orbit を $B$ とすると $t-(|X|, k, \lambda)$ デザインができる。
$X^{(1)}=\{(x_{1},x_{2},$ $\cdots,x_{l})|x_{1},x_{2},$ $\cdots,x\iota\in$ X(相異なる)とする。 スーパースキームの定義にある分割$\Pi^{l}=\{R^{l}R^{l}, \cdots,R_{d_{l}}^{l}\}$ が、 ある $m$ で $R_{m}^{l}=X^{(t)}$ となるとき、 l-homogeneous であると定める。 可移拡大は存在しないが、 スーパースキームが構成できたとき、 orbit の様な集合を考えてデザインを作る。以下に、例で示す。
$G$を $X$ の$\{x_{1},x_{2}, \cdots, x_{l}\}^{g}=\{x_{1}^{g},x_{2}^{g}, \cdots, x_{l}^{g}\}$

$l$

$t$

$\{y_{1},y_{2}, \cdots, y_{1}\}$$t$$\{y_{1}, y_{2}, \cdots,y_{l}\}$

$k$

$\}$

$X=\{1,2, \cdots, 20,21\},$ $|X|=21,$ $G_{2}i=PSL(2,19)$ている。このとき、$\Pi^{(4)}=\{R_{1}^{4}, R_{2}^{4}\}$$[x, y, z,w_{9}]\in R_{1}^{4}$$G_{21}$, P41,4

on$X\backslash \{21\}$とする。 2 重可移で 3-homogeneous となっから、 3-homogeneous 4-superschemes が得られるが、群$=$$G_{21}$の可移拡大は存在しない。

9、つまり、 orbit(の様な集合) 2 個で、 9 個の 4 点対が $[X, y,z,w_{1}],$ $[x, y, z, w_{2}],$となるので、 9 点部分集合する部分群の orbit と考える。 $x,$ $y,$$z$$[w_{1},w_{2}, \cdots ,w_{9}]$を、 可移拡大が存在した場合に、 $x,$ $y,$$z$$\cdots$,を固定を動かしたときにできるこの 9 点部分集合は 1520 個が 3 回繰返して現れ、 570 個が 6 回繰返して現れる。 これらをブロックとすると、 3-design (with repeated blocks) が得られる。 群の拡大が存在したら、

4$arrow$デザインになっているはずであるが、 そうなっていない。

A Generalization
Let a group$G_{0}$

be t-homogeneous on$X\backslash \{0\}$. Choose some orbits of$G_{0}$

on the $(k+1)$ -point subsets

of $X$ such thata orbit such that $0\in b_{0}\in B_{0}$ ,.
B\’i orbits such thatLet
be the orders of the stabilizers of $(k+1)$ -point subsets of these orbits inIn the followin theorem
means that any block inis repeated times.
$B_{0}$$0\not\in b_{1}\in B_{1}\cup B_{1}’$$B_{1},$$g_{0},$$g_{1},$$g_{1}’$$g$$c_{j}B_{j}$$B_{J}$$c_{j}$$G_{0}$, respectively.

158
定理 1([9])Let $B=c_{0}B_{0}\cup c_{1}B_{1}\cup d_{1}B_{1}’$ , where$c_{0},$$c_{1}$

and$d_{1}$satisfy$\frac{(n-k)c_{0}}{(k+1)g0}=\frac{c_{1}}{g_{1}}+\frac{d_{1}}{f_{1}}$.

Then $(X, B)$ is a $t-(n+1, k+1, \lambda)$ design, where$\lambda=\frac{c_{0}g(t-k1)}{g_{0}(t-n1)}$

In particular, if $d_{1}=0$ , then $B=c_{0}B_{0}\cup c_{1}B_{1}$ and the a bove condition becomes$\frac{c_{1}}{c_{0}}=\frac{g_{1}(n-k)}{g_{0}(k+1)}$.

Proof.
$\frac{\#\{(T,b)|Tt- subset\not\supset 0)b\in c_{0}B_{0}\cup c_{1}B_{1}\cup d_{1}B_{1}’\}}{(\begin{array}{l}nt\end{array})}$$=$$\frac{\frac c_{1}g_{1}g(\begin{array}{l}k+lt\end{array})+\frac{d_{1}g}{g_{1(}}(kt+1)+\frac{c_{0}g}{g_{0}}(\begin{array}{l}kt\end{array})}{n,t)}$$=$$\frac{\frac{k+1}{t}(\begin{array}{l}kt-1\end{array})\{\frac{c_{1}g}{g_{1}}+\frac{d_{1}g}{g_{1}’1}\}+\frac{k-t+1}{arrow 1n)t}\frac{c_{0}g}{g_{0}}(\begin{array}{l}kt-1\end{array})}{\frac{n-t+}{t}(_{t}}$$=$$\frac{\{\frac{k+1}{t}\{\frac{c_{1}g}{g_{1}}+\frac{k-t+1}{t}\frac{c_{0}g}{g_{0}}\}(\begin{array}{l}kt-1\end{array})}{\frac{n-t+1\frac{d_{1}g}{g_{1}’}\}+}{t}(\begin{array}{l}nt-1\end{array})}$.

.

$\frac{\#\{(T,b)|Tt- subset\ni 0,b\in c_{0}B_{0}\}}{(\begin{array}{l}nt-l\end{array})}=\frac{\frac c_{0}g_{0}g(t-k1)}{(_{t-1}n)}$Exmple: $G=PSL(2, q)$ or $PGL(2, q)$ acting on projective line $P=\{1,2, \cdots, q+1\}$ . If $G=PSL(2,$ (1),be the stabilizer of the points 1 and 2
we assume that $q=3mod 4$ Then $G$ is 3-homogeneous. Let$G_{1,2}$in$G$. We assume $q=$ lmod6. Then $3|q-1$ .

$\delta 1(q-1)$

has subgroups of order 3 and of order $B1(q-1)haviJag$$l1(q-1)$ respectively. We use some of these orbits toof3
lengthorbits of length and two orbits$G_{1,2}$159
construct blocks.
Set
orbits of length $3\cup\{0,1,2\}$$b_{1}= \bigcup_{B}^{1}(q-1)$ orbits of length 3$b_{1}’=a$ orbit of length
should be $g_{0}=3c_{0}$ ,Then $k+1= \frac{1}{2}(q-1)$ (block size). The orders of the stabilizers of the blocks$g_{1}=3c_{1},$, respectively. Set $B=$ co. Then we have$b_{0}= \cup\frac{1}{6}(q-7)$$\frac{1}{2}(q-1)$$b_{0},$$g_{1}’=\lrcorner^{c’}2(q-1)$$b_{1},$$b_{1}’$$B_{0}\cup c_{1}B_{1}\cup d_{1}B_{1}’$$\frac{(n-k)c_{0}}{(k+1)g_{0}}=\frac{q+1-\frac{1}{21}(q-3)}{\frac{1}{2}(q-)\cross 3}=\frac{q+5}{3(q-1)}$$\frac{c_{1}}{g_{1}}+\frac{d_{\iota}}{g_{1}}=\frac{1}{3}+\frac{2}{q-1}=\frac{q+5}{3(q-1)}$$|G|= \frac{1}{m}(q+1)q(q-1)$, where $m=2$ or 1 according as $G=PSL(2, q)$ or $PGL(2, q)$ .
$\lambda=\frac{(q-1)(q-3)(q-5)}{12m}$定理 2([8])$(PU\{0\}, B)$

is a $3-(q+2, \frac{1}{2}(q-1), \varpi_{\overline{m}}^{1}(q-1)(q-3)(q-5))$ desigii.

is as above. Similarly we chose 3 subsets of PU$g_{1}=c_{1}$ ,$g_{0}=c_{0}$ ,$G$$\{0\}$of size- $(q+1)$ so that the stabilizers are of order$g_{1}’=_{2}^{c’}\lrcorner(q+1)$

定理 3$(PU\{0\}, B)$5

is a $3-(q+2,1f(q+1), \tau_{\overline{m}}^{1}(q-1)^{2}(q-3))$ design.

ExperimentsWe use GAP systm [3] in our experiments. $G=PSL(2,31)=PrimltiveGroup(32,4)$ . Then we canchoose the blocks of size $\frac{1}{2}(q-1)=15$ so that the stabilizers are of order 3, 3, 15. Therefore we havetaht $(PU\{33\}, B)$ is asimple $3-(33,15,910)$ design.
$G=PGL(2,25)=PrimitiveGroup(26,2)$ . We can choose the blocks of size $(q-1)=12$ so that thestabilizers are of order 6, 6, 24. So by Theorm 2 $c_{0}=c_{1}=d_{1}=2$ , which implies $B=2B_{0}\cup 2B_{1}\cup 2B_{1}’$ .
In this csse, if we set $B=B_{0}\cup B_{1}\cup B_{1}’$ , we have asimple $S-(27,12,440)$ daeign.
$G=PGL(2,25)=Primi$ tiveGroup(26, 2). We can choose the blocks of size $\frac{1}{2}(q+1)=13$ so that thestabilizers are of order 2, 2and 26. So by Theorem 3 $c_{0}=c_{1}=d_{1}=2$ . We have asimple 3-(27,13,1584)
design if we set $B=B_{0}\cup B_{1}\cup B_{1}’$ .
$G=PSL(2,19)=Primitlv\epsilon Group(20,1)$ . We can choose subsets of size $(q+1)=10$ so that thestabilizers are of order 1, 1, 10. So by Theorem 3 $c_{0}=c_{1}=d_{1}=1$ We have asimple&(21, 10, 648)
design.
The subgroups of $PSL(2, q)$ are well known (cf. [2]). Probably we will be able to get simple $3-(q+2, k, \lambda)$
designs, $k=\mathfrak{T}1(q-1)$ and- $(q+1)$ , generally ([9]).
$G=AGL(2,5)=Prlmitiv\epsilon Group(25,22)$ . $|G|=12000$ We can choose
and of size 5 so that theThenofstabihizers these blocks are of order 80 and 400.

2151

$b_{0}$$\frac{g_{1}(n-k)}{g_{0}(k+1)}=\frac{400(25-4)}{80(4+1)}=21$.

$b_{1}$

160
So if we set $B=B_{0}\cup 21B_{1}$ , then we have a 2-(26,5,24) design by Theorem 1. We can also choose subsetsof size 6 so that he stabilizers are of order 400 and 12. Then$\frac{g_{1}(n-k)}{g_{0}(k+1)}=\frac{12(25-5)}{400(5+1)}=\frac{1}{10}$.

So if we set $B=10B_{0}\cup B_{1}$ , then we have a 2-(26,6,60) design.
G MathieuGroup(24) $=\langle(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23),$ $(3,17$ ,10, 7, $9)(4,13,14,19,5)(8,18,11,12, 23)$ (15, 20, 22, 21, 16), (1, 24)(2, 23) (3, 12)(4, 16)(5, 18)(6, 10)(7, 20) ,14)(9, 21)(11, 17) (13, 22) 15,acts on 1, 2, $\cdots,24\}$ . We take 25 as the aclin the GAP library.
ditional point and set$=$$|_{\backslash }^{(}8$$($$G$$19)\rangle$$b_{0}$$=$$b_{1}$$=$$b_{1}’$

$=$

$\{$

{3, 4, 6, 7, 10, 12, 13, 14, 17, 21, 22, 25},
{3, 4, 5, 6, 7, 10, 11, 12, 14, 18, 21, 23} and{1, 2, 3, 4, 5, 6, 8, 11, 13, 15, 18, 24}.

The stabillzers of these blocks are $oi$ order 7920, 95040
and $d_{1}=4$ and set $B=5B_{0}\cup 10B_{1}\cup 4B_{1}’$ . Thenand 6912 respectively. Set co $=5,$ $c_{1}=$ ]$.0$$\frac{(24-11)x5}{(11+1)x7920}=\frac{13}{19008}=\frac{10}{95040}+\frac{4}{6912}$

and $\lambda=4800$ . So $(X, B)$ is a 5-(25,12,4800) design, since$G$

is 5-homogeneous. Moreover we see that$(X, B)$ is a 6-(25,12,1680) design.

が決まっていれば、 コンピュータを使ったデザインの構成は様々に行われている (例えば、 [1])。
ここには、 定理の応用例としての実験を示した。 また、 デザインについては [4] 等を参照された V
サイズ

$v$

$\backslash$。

参考文献[1] A. Betten, E. Haberberger, R. Laue, A. Wassemann, DISCRETA- a program to constmct t-designs
with prescribed automorphism group. http: $//www,mathe2.uni$ -bayreuth.de/discreta/[2] P. J. Cameron, H.R.Maimani, G.R.Omidi and B. Tayfeh-Rezaie, 3-Designs from PSL 2,Math., 3063-3073,306 (2006).
$($$q)$. Discrete[3] The GAP Groups. Gap- groups, algorithms and programming, version 4. Lehrstuhl $D$ fir Mathematik,
Rheinisch Westfalische Technische Hochschule, Aachen, Germany and School of Mathematical andComputational Sciences, Univ. St. Andrews, Scotland, 2000.
[4] G. B. Khosrovsh 下上 a and R. Laue, t-Designs with $t\geq 3$ , in Handbook of Combinatorial Designs (2nd Edition), $CRC$ Press Series on Discrete Mathematics and its Applications, C. J. ColbournJ. H. Dinitz (eds.) CRC Press, Boca Raton, FL, (2006) 79-101.
$an_{\lfloor}d$[5] 宮本泉, アソシエーションスキームの拡張と 2 重可移群の計算. Computer Algebra, Algorithms, Implementations and Applications, 数理解析研究所講究録 185-189, 1394 (2004)[6] 宮本泉, 置換群の可移拡大の計算法, Computer Algebra, Algorithms, Implementations and Applications,
数理解析研究所講究録 35-39, 1456 (2005)[7] I. Miymoto, A Computation of Some Multiply Homogeneous Superschemes from Transitive Pemutation Groups. In: Brown, C.W. (ed) Proceedings of the 2007 Intemational Symposium on Symbolicand Algebraic Computation. ACM press, 293-298 (2007)

161[8] I. Miyamoto, A construction of designs from $PSL(2,q)$ and $PGL(2,q),$ $q\equiv 1(mod 6)$ , on $q+2$
points. to appear in Algorithmic Algebraic Combinatorics and Grobner Bases, edited by G. Jones, .
Jurisic, M. Muzychuk and I. Ponomarenko Springer.
$A$[9] I. Miyamoto, A construction of designs on $n+1$ points $hom$ multiply homogeneous permutationgroups of degree . in preparation.
$n$