数理解析研究所講究録
991 巻 1997 年 103-107

103

Association schemes with a prime numberof points
九大数理研
主定理 1

平坂

貢(Mitsugu Hirasaka)を可換なアソシエーションスキームで、 $|X|$が素数と仮定する。 もし valency が 3 の telahon が存在するならば、 X はvalency が 3 の cyclotomic scheme と同型である。
$\mathcal{X}=(X, \{h\}_{0\leq i\leq d})$「素数位数の群は巡回群のみである。」 このことはごく簡単な結果であるが、上の群をアソシエーションスキームに置き換えると、 どうなるか? というのがそもそもの動機である。 このことはという群の作用を仮定した対象に限定すれば、群の場合と同様に、 cyclotomic scheme と同型という結果が得られるが (, 参照)」 を仮定しないと問題は極めて厄介なものになる。実際、 $|X|=19$ で、 nontranslation scheme の存在が認$\mathrm{r}\mathrm{t}\mathrm{r}\bm{\mathrm{t}}\mathrm{S}\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{i}_{\mathrm{o}\mathrm{n}\rfloor}$$[5],\mathrm{p}.66$

められていて ( $[8|$ , 参照)$\mathrm{r}_{\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{s}}1\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$、が大きくなるにつれ、 $d=2$ のアソシエ一ショ
ンスキームの同型類も飛躍的に大きくなるものと予想される。 このことは組み合わせ的見地から見た困難さを物語っていて、translation と、$|X|$$\mathrm{n}\mathrm{o}\dot{\mathrm{n}}\mathrm{t}\mathrm{r}\mathfrak{W}\mathrm{S}\mathrm{l}\mathrm{a},\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$の境界を明白にすることの意義を立証するものである。
今回の主定理は valency が十分小さいときの素数点上のアソシエーションスキームの–意性を述べたものであるが、 valency が 4 以上のときどうなるかは今後の研究課題である。勿論、 $|X|=19$ のときに nOntrtslatiOn schemeが存在しているので、 上限は存在するのだが、 これは d $=2$ の場合なので、この diameter と valency との関わり合いも注目すべき点である。
以上は構造定数も含めた組み合わせ構造に関する議論であるが、 構造定数のみを考えることも興味深い。例えば $d=2$ のアソシエーションスキームの構造定数は–意に決まる。 $d\geq 3$ に関しては未解決である。 しかし $d=3$のときは $k_{1}=k_{2}=k_{3}$ を仮定すると、構造定数は–意という結果 ( , 参照)$[7|$が示されているので、 $k_{1}=k_{2}=k_{3}$ ということを $|X|$ が素数という条件から導けないか、 と模索中である。
.
用語の定義は今から述べるが、詳しくは [2],[5] を参照されたし。 .
$\cdot$$|$104

定義 1を有限集合として、 $k(i=0, \ldots, d)$ を X X の部分集合とする。
各瓦に関する X の元で順序付けられた隣接行列 A, を次のように定義する。
$X$$\cross$$(A_{i})_{xy}:=\{$1if $(x, y)\in k$$0$

OtherWiSe次に述べる条件 ), ), ), ) を満たすとき $\mathcal{X}=(X, \{k\}_{i=0,\ldots,d})$ はアソシエ一ションスキームと呼ばれる。
$\mathrm{i}$$\mathrm{i}\mathrm{i}$$\mathrm{i}\mathrm{i}\mathrm{i}$$\mathrm{i}\mathrm{v}$i) $A_{0}=I$ , ただし I は単位行列。
ii) $A_{0}+\ldots+A_{d}=J$ , ただし J は成分がすべて 1 の行列。
iii) 任意の に対して、となるような $i’\in\{0,1, \ldots, d\}$ が存在する。
iV) 任意の的に対して、次が成り立つ。
$i$${}^{t}A_{i}=A_{i’}$

ヨ$A_{i}A_{j}= \sum p_{ij}^{h}A_{h}$.

$h=0$

さらに、 X が次の V) を満たすとき、 可換であるという。
V) 任意の $i,j\in\{0_{)}1, \ldots, d\}$ に対して、 $A_{i}A_{j}=A_{j}A_{i}$ .
X が次の vi) を満たすときに対称であるという。
vi) 任意の $i\in\{0,1, ..., d\},$.
$A_{i}^{t}=A_{i}$定義 2 (CyClOtOmic SChemes)

を位数が q の有限体とする。 ただし q は素数幕である。 を Fq の乗法群の生成元として、をで生成される部分群とする。ただし は $q-1$ の約数である。そのとき $X=F_{q}\text{上の}$$\xi$$F_{q}$$\xi^{d}$$K\subset F_{q}^{*}$$d$$cycl_{\mathit{0}}tomic$

scheme は$R_{\dot{4}}=\{(x_{)}y)|y-X\in\xi^{i}K\}(1\leq i\leq d)$.

によって定義される。
定義 3(scheme) アソシエーションスキーム
に対して、 $X$ がアーベル群の構造を持っていて、任意の$?\mathrm{k}\mathrm{a}\mathrm{n}\mathrm{s}\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{i}_{\mathrm{o}\mathrm{n}}$$\mathcal{X}=(X, \{h\}0\leq i\leq \text{ヨ})$$oe\iota_{ati_{or}R}$に対して、(X, ) $\in R_{i}\Leftrightarrow(x+z, y+z)\in\hslash$$y$が成り立つとき $tmnS\iota_{a}tion$ SCheme と呼ばれる。

それでは主定理の証明の概略を述べる。 以下で、なアソシエーションスキームで、 $|X|$ が素数と仮定する。

$\mathcal{X}=(X, \{R_{i}\}_{0\leq i}\leq d)$

を可換

105

(i)
(ii)

「 $|X|=7\Leftrightarrow p_{jj}^{j}=1$ for「$(\mathrm{i}),(\mathrm{i}\mathrm{i})$$\exists R_{m}\mathrm{s}.\mathrm{t}$より、. $k_{m}=3,$$A_{1},$ $A_{2}$

を

some

$p_{mm}^{m’}=2$$R_{1},$ $R_{2}$$R_{j}$

with$k_{j}=3\mathrm{J}$を示す。

」 を示す。

に関する隣接行列とした時、」 を仮定してよいことが分かる。

$\mathrm{r}A_{1}^{2}=2A_{1}t+A_{2}$

ただし $k_{1}=k_{2}=_{3},$ $A_{2}\not\in\{A_{1,1}A^{t}\}$

定義 4X の元の列 $(x_{0}, x_{1,,n}\ldots X)$ は「 $(x_{i}, x_{i+}1)\in R_{1}(i=0,1, \cdots, n-1)$
かつ $(X_{i}, X_{i+}2)\in R_{1}(i=0,1, \cdots, n-2)$ 」 を満たすときに長さの Chain と呼ばれる。
$\mathrm{n}$定義 5{Bn}l5n を次の漸化式で定義された行列の集合とする。
$B_{1}:=A_{1,2}B:=A_{2},$ $B3:=A1A2-A1A^{t}1+3A0$$B_{n}:^{=}A_{1}BA_{1}^{t}n-1^{-}B_{n}-_{2}+B_{n^{-3}}.$ ’(iii)$\mathrm{r}_{\mathrm{C}}\mathrm{h}\mathrm{a}\mathrm{i}\mathrm{n}$$n\geq 4$(1)の長さは relation を characterize すること」 を示す。すなわち、

命題 1 $B_{i}(1\leq i\leq n)$ が単位行列でない X の隣接行列と仮定する。そ.のとき次が成り立っ。
から y に向かう唯–つの長さ の Chain が存在する。
(X, )ただし Rn はに対応するiOn である。
$y$$\in R_{n}\Leftrightarrow x$$\mathrm{n}$$oela\dot{t}$$B_{n}$$(iv.)$

この chain を用いて、分は次の$(\mathrm{a}),(\mathrm{b})$$(a)\{x_{i}\}0\leq i\leq_{P^{-1}},$グラフの構造を決定する。 に関する連結成のいずれかである。
は素数。
は Chaino$p$$R_{1^{-}}$$R_{1}$$(X_{0}, X_{1,1}\ldots, X_{p}-, X_{0})$106$(b)\{X_{ij},\}.0\leq i,j\leq p-1,$$P$

は素数 a 任意の , に対して、 $(x_{i0,.i1},X,,. \cdots,X_{i}.’ x,0)p-1,i$ ,は Chaino$i^{j}$$(x0.\dot{\tau}’ x1\cdot\dot{\tau}’\ldots,X\mathrm{n}-1\cdot\dot{\tau}’ X0^{\dot{\eta}}.)$$\sim$(i), $(ii^{),(i}ii^{)}, (iv)$ までの議論は
つ「$\mathcal{X}$haS$\mathrm{n}\mathrm{o}\mathrm{s}^{\mathrm{y}}\mathrm{m}\mathrm{m}\mathrm{e}\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{c}\mathrm{r}\mathrm{e}\mathrm{l}\mathrm{a}.\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$ても成り立つ。

が素数という条件を 「」 かという条件に置き換え
with odd$|X’|$$\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{c}^{\mathrm{y}.\rfloor}$.

(V) $|X|$ は素数なので$\mathcal{X}\mathrm{i}\mathrm{S}^{\mathrm{p}}\mathrm{r}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{v}\mathrm{e}\cdot$

$.=$

.

.

(b) は不適。 (iii) により、 (a) は$\mathrm{t}\mathrm{r}\bm{\mathrm{t}}\mathrm{S}\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$SChemeである。
$\text{次}.\dot{\text{の}}$命題はすでに証明されている ($[5]_{\mathrm{P}},.66$, 参照)。

命題 2 素数点からなる $tmns\iota ation$ SCheme は $Cyc\iota otomic$ SCheme である。

上の命題より、 証明が終わる。
構造定数の議論については H.I.
らが「
table

$\mathrm{B}\mathrm{l}\mathrm{a}\mathrm{u}_{\text{、}}\mathrm{Z}\cdot \mathrm{A}\mathrm{r}\mathrm{a}\mathrm{d}_{\text{、}}$

E.

$\mathrm{F}\mathrm{i}\mathrm{s}\mathrm{m}\mathrm{a}\mathrm{n}_{\text{、}}\mathrm{V}\cdot \mathrm{M}\mathrm{i}\mathrm{l}\mathrm{o}\mathrm{S}\mathrm{l}\mathrm{a}\mathrm{v}\mathrm{S}\mathrm{k}\mathrm{y}_{\text{、}}$

に関する結果を出している。
$[1],[3],[4^{]}$ , 参照) Integral table algebra とは自然数の構造定数を持つ基底ではられた代数で、いくつかの条件を満たすものである。アソシエーションスキームの隣接行列ではられる BOse-Mesner algebra もまた Integral table algebra の例である。彼らは内積や整数条件を用いて結果を導いている。 定義 5 の漸化式も彼らの論文の引用で、 この漸化式を用いることで、 Statement をかなり平易にすることができた。
$\mathrm{M}\cdot \mathrm{M}\mathrm{u}\mathrm{z}^{\mathrm{y}}\mathrm{c}\mathrm{h}\mathrm{u}\mathrm{k}$$\mathrm{I}\mathrm{n}\mathrm{t}\mathrm{e}^{\mathrm{g}}\mathrm{r}\mathrm{a}\mathrm{l}$$\mathrm{a}1^{\mathrm{g}}\mathrm{e}\mathrm{b}\mathrm{r}\mathrm{a}^{\rfloor}$$($References[1] Z.Arad, E.Fisman, V.Miloslavsky, M.Muzychuk, On antisymmetrichomogeneous integer table algebras, preprint.

107[.2] E.Bannai and T.Ito, Algebraic Combinatorics$\mathrm{B}\mathrm{e}\mathrm{n}\mathrm{j}\mathrm{a}\mathrm{m}\mathrm{i}\mathrm{n}/\mathrm{C}\mathrm{u}\mathrm{m}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{g}\mathrm{s}$[3]$\mathrm{H}.\mathrm{I}$, Menlo Park,$\mathrm{C}\mathrm{A}$$\mathrm{I}:\mathrm{A}\mathrm{S}\mathrm{S}\mathrm{o}\mathrm{C}\mathrm{i}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$schemes,, 1984.

. Blau, Integral Table Algebras, Affine Diagrams, Analysys of De-gree Two, J. Algebra 178, 872-918 (1995)[4]$\mathrm{H}.\mathrm{I}$. Blau, On Table Algebras and Applications to Finite Group The-

ory, J. Algebra 138, 137-185 (1991)[5][6].Brouwer,.Cohen and A.Neumaier,
Graphs, Springer-Verlag,1989.

$\mathrm{A}.\mathrm{E}$$\mathrm{A}.\mathrm{M}$.Godsil, Algebraic
matics$\mathrm{C}.\mathrm{D}$Distance Regular.ioe, Champman and Hall Mathe-$\mathrm{c}_{\mathrm{o}\mathrm{m}}\mathrm{b}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{t}_{\mathrm{o}\mathrm{r}}$[7] M.Hall, Jr. Combinatorial Theory, second edition, A WileyInterscience Publication.
[8] Akihide Hanaki and Izumi Miyamoto, private communication.

[9] E.Nomiyama, Classification of association schemes with at most tenvertices, Kyushu J. of Math.49(1995),163-195.