Steiner三重系
概要
Steiner三重系（Steiner triple system）とは、有限集合の 3 元部分集合の族で、相異なるどの 2 点もちょうど 1 つの族の元に含まれるものであり、Steiner 系 $S(2,3,v)$ にあたる。位数 $v$ の三重系が存在するのは $v\equiv1,3\pmod6$ のときであり、そのときに限る（Kirkman の存在定理）。十分性は、可換準群を 3 枚重ねる Bose と Skolem の構成で示される。三重系は Steiner 準群と一対一に対応し、その直積から位数の積の三重系が得られる。
Steiner三重系（Steiner triple system）は、有限集合の 3 元部分集合の族で、相異なるどの 2 点もちょうど 1 つの族の元に含まれるものである。Steiner系 の記号では $S(2,3,v)$ にあたる。7 点の Fano平面 がその代表例である。
点の個数 $v$ を三重系の位数という。2 点の組を数えると、位数は $6$ で割って $1$ か $3$ 余る数に限られる。逆にそのようなすべての $v$ に三重系があることを T. P. Kirkman が 1847 年に示した（HL13 p. 1）。この記事では、この存在定理を、位数 $6n+3$ では Bose の構成で、位数 $6n+1$ では Skolem の構成で証明する。どちらも、位数 $2n+1$ または $2n$ の可換な準群（九九の表がラテン方陣になる演算）を 3 枚重ねて三重系を作る。
三重系は、2 点 $a,b$ に「同じ三重に入る第 3 の点」を対応させる演算によって、Steiner 準群という代数系と同じものになる（thm-sts-squag）。準群の直積から、位数の積の三重系も得られる。
定義と必要条件
$v=1$ では $\mathcal B=\emptyset$、$v=3$ では $\mathcal B=\{X\}$ が Steiner三重系である。$v=2$ のものはない。
$(X,\mathcal B)$ を $\mathrm{STS}(v)$ とする。各点を含む三重はちょうど $(v-1)/2$ 個、三重の個数は $|\mathcal B|=v(v-1)/6$ である。したがって $v\equiv1$ または $3\pmod6$ である（BS12 Chapter III, Theorem 1.2）。
点 $x$ を含む三重を $T_1,\dots,T_r$ とすると、$T_k\setminus\{x\}$ は互いに交わらない（交われば 2 点を含む三重が 2 つになる）2 元集合で、それらの和は $X\setminus\{x\}$ である（$x$ と他の点を含む三重があるから）。よって $v-1=2r$ である。各三重は 2 点の組を 3 つ含み、各組はちょうど 1 つの三重に含まれるので $\binom v2=3|\mathcal B|$ である。$v$ は奇数で、$v(v-1)/6$ が整数なので $v(v-1)\equiv0\pmod3$、つまり $v\equiv0,1\pmod3$ である。$v$ を $6$ で割った余りのうち奇数で $3$ を法として $0$ か $1$ になるのは $1$ と $3$ である。$\square$
Steiner系 の系「割り算の条件」の $t=2$、$k=3$ の場合でもある。三重系であることを確かめるときは、次の数え上げが便利である。
$v$ 点の集合 $X$ の 3 元部分集合の列 $B_1,\dots,B_b$（重複を許す）が、$X$ の相異なる任意の 2 点を含む $B_k$ を少なくとも 1 つもち、$b=v(v-1)/6$ であるとする。このとき $B_k$ はどの 2 つも異なり、$(X,\{B_1,\dots,B_b\})$ は $\mathrm{STS}(v)$ である。
組 $(k,P)$（$P$ は $B_k$ に含まれる 2 点の組）の個数は $3b=\binom v2$ である。各組 $P$ は少なくとも 1 回現れ、組の総数も $\binom v2$ なので、各組はちょうど 1 回現れる。2 つの $B_k$ が等しければ、それらに含まれる組が 2 回現れるので、$B_k$ は相異なる。$\square$
Steiner 準群
集合 $A$ 上の二項演算 $\cdot$ が、すべての $x,y\in A$ について
$$
\text{(Sq1)}\ x\cdot x=x,\qquad \text{(Sq2)}\ x\cdot y=y\cdot x,\qquad \text{(Sq3)}\ x\cdot(x\cdot y)=y
$$
を満たすとき、$(A,\cdot)$ を Steiner準群（squag）という（BS12 Chapter III, Definition 1.3）。
(Sq3) から、$a$ を固定した $y\mapsto a\cdot y$ は自分自身が逆写像になる全単射である。よって Steiner準群の九九の表（$A$ が有限のとき）は、各行・各列に各元がちょうど 1 回ずつ現れる対称な ラテン方陣 で、対角成分は $x\cdot x=x$ である。
有限集合 $A$ について、次の二つの対応は互いに逆で、$A$ 上の Steiner三重系の全体と $A$ 上の Steiner準群の演算の全体の間の全単射を与える（BS12 Chapter III, §1 の構成と Theorem 1.4）。
- 三重系 $\mathcal B$ に対し、$a\ne b$ なら $a\cdot b$ を $a,b$ を含む三重の第 3 の点、$a\cdot a:=a$ とする。
- Steiner準群 $\cdot$ に対し、相異なる $a,b$ について $\{a,b,a\cdot b\}$ の形の集合の全体を $\mathcal B$ とする。
1 の演算が Steiner準群であること：(Sq1) は定義、(Sq2) は三重が $a,b$ について対称に決まることによる。(Sq3) は、$x=y$ なら (Sq1)、$x\ne y$ なら $z:=x\cdot y$ について $\{x,y,z\}$ が三重なので $x\cdot z=y$ による。
2 が三重系であること：$a\ne b$、$c:=a\cdot b$ とする。$c=a$ なら (Sq3) と (Sq1) から $b=a\cdot(a\cdot b)=a\cdot a=a$ となり矛盾するので $c\ne a$、(Sq2) から同様に $c\ne b$ で、$\{a,b,c\}$ は 3 元集合である。(Sq3) と (Sq2) から $a\cdot c=b$、$b\cdot c=b\cdot(b\cdot a)=a$ なので、この集合のどの 2 点の積も第 3 の点である。よって 3 元集合 $\{a,b,c\}\in\mathcal B$ はどの 2 点 $p,q$ からも $\{p,q,p\cdot q\}$ として決まり、$a,b$ を含む $\mathcal B$ の元は $\{a,b,a\cdot b\}$ だけである。
互いに逆であること：三重系 $\mathcal B$ から 1 で作った演算の $\{a,b,a\cdot b\}$ はちょうど $a,b$ を含む三重なので、2 で $\mathcal B$ に戻る。Steiner準群から 2 で作った三重系では、$a\ne b$ を含む三重は $\{a,b,a\cdot b\}$ なので、1 で元の演算に戻る（対角は (Sq1)）。$\square$
Steiner準群の条件は等式だけなので、直積の上でも成り立つ。これから三重系の積の構成が得られる。
$\mathrm{STS}(v_1)$ と $\mathrm{STS}(v_2)$ があれば $\mathrm{STS}(v_1v_2)$ がある。
thm-sts-squag で対応する Steiner準群 $(A_1,\cdot)$、$(A_2,\cdot)$ をとり、$A_1\times A_2$ に成分ごとの演算 $(a_1,a_2)\cdot(b_1,b_2):=(a_1\cdot b_1,a_2\cdot b_2)$ を入れる。(Sq1)〜(Sq3) は成分ごとに成り立つので、$A_1\times A_2$ は Steiner準群であり、thm-sts-squag の 2 により位数 $v_1v_2$ の三重系を定める。$\square$
たとえば $\mathrm{STS}(9)$ と $\mathrm{STS}(3)$ から $\mathrm{STS}(27)$、$\mathrm{STS}(7)$ どうしから $\mathrm{STS}(49)$ が得られる。積の三重は、$\{(a_1,a_2),(b_1,a_2),(a_1\cdot b_1,a_2)\}$ のように一方の成分が一定で他方の成分が三重をなすものと、二つの成分がともに三重をなすものからなる。
存在定理
構成には、位数 $m$ の集合上の可換な演算 $\circ$ で、九九の表がラテン方陣になるもの（可換準群）を使う。$x\circ x=x$ がすべての $x$ で成り立つとき冪等という。
$n\ge1$ とする。
- $m=2n+1$ のとき、$\mathbb Z/m\mathbb Z$ 上の $x\circ y:=(n+1)(x+y)$ は冪等な可換準群である。
- $m=2n$ のとき、$0\le s< 2n$ について $\phi(s):=s/2$（$s$ が偶数）、$\phi(s):=(s-1)/2+n$（$s$ が奇数）とおき、$\mathbb Z/m\mathbb Z$ の元を代表 $0,\dots,2n-1$ で表して $x\circ y:=\phi(x+y)$ とする。これは可換準群で、$0\le x< n$ について $x\circ x=(x+n)\circ(x+n)=x$ を満たす。
1．$2(n+1)=m+1\equiv1$ なので $n+1$ は $2$ の逆元であり、$x\circ x=(n+1)\cdot2x=x$ である。可換性は明らかで、$y\mapsto(n+1)(x+y)$ は $y\mapsto x+y$ と可逆元倍の合成なので全単射である（合同式）。2．$\phi$ は偶数 $0,2,\dots,2n-2$ を $0,\dots,n-1$ に、奇数 $1,3,\dots,2n-1$ を $n,\dots,2n-1$ に送る全単射なので、$y\mapsto\phi(x+y)$ は全単射で、可換性は明らかである。$0\le x< n$ なら $2x$ と $2(x+n)\equiv2x$ はともに代表 $2x$ をもち、$\phi(2x)=x$ である。$\square$
2 の性質 $x\circ x=(x+n)\circ(x+n)=x$ を半冪等という。偶数の位数では冪等な可換準群は存在しない（rem-sts-counterexamples の 1 行目）ので、Skolem の構成ではこの半冪等なもので代用する。
要点：点の集合を $Q\times\{0,1,2\}$（$Q$ は準群）とし、同じ段の 2 点 $(x,i),(y,i)$ に次の段の点 $(x\circ y,i+1)$ を添えた三重と、縦に並ぶ三重をとる。段 $i$ と段 $i+1$ の 2 点の組は、準群の方程式 $x\circ y=z$ がただ 1 つの解をもつことから覆われる。
詳しい証明を開く
必要性は prop-sts-necessary である。段の番号 $i$ は $\mathbb Z/3\mathbb Z$ の元とする。$v=1,3$ は上で見たので、$n\ge1$ とする。
$v=6n+3$（Bose の構成）。$Q=\mathbb Z/(2n+1)\mathbb Z$ に lem-sts-quasigroups の 1 の演算を入れ、$X=Q\times\{0,1,2\}$ とする。三重の列として、(i) $\{(x,0),(x,1),(x,2)\}$（$x\in Q$）と、(ii) $\{(x,i),(y,i),(x\circ y,i+1)\}$（$\{x,y\}$ は $Q$ の 2 元部分集合、$i\in\mathbb Z/3\mathbb Z$）をとる。(ii) は段が違うので 3 元集合である。個数は $(2n+1)+3\binom{2n+1}2=(2n+1)(3n+1)=v(v-1)/6$ である。2 点の組が覆われること：同じ段の $(x,i),(y,i)$ は (ii)、$(x,i),(x,i')$ は (i) が含む。$x\ne z$ の $(x,i),(z,i+1)$ について、$x\circ y=z$ となる $y$ がただ 1 つあり、$x\circ x=x\ne z$ なので $y\ne x$ であって、(ii) の $\{(x,i),(y,i),(z,i+1)\}$ が含む。段の差は $\pm1$ しかないので、これですべての組が覆われる。lem-sts-count により $\mathrm{STS}(v)$ である。
$v=6n+1$（Skolem の構成）。$Q=\mathbb Z/2n\mathbb Z$ に lem-sts-quasigroups の 2 の演算を入れ、新しい点 $\infty$ をとって $X=\{\infty\}\cup Q\times\{0,1,2\}$ とする。三重の列として、(i) $\{(x,0),(x,1),(x,2)\}$（$0\le x< n$）、(ii) $\{\infty,(x+n,i),(x,i+1)\}$（$0\le x< n$、$i\in\mathbb Z/3\mathbb Z$）、(iii) $\{(x,i),(y,i),(x\circ y,i+1)\}$（$\{x,y\}$ は $Q$ の 2 元部分集合）をとる。個数は $n+3n+3\binom{2n}2=n(6n+1)=v(v-1)/6$ である。$\infty$ と $(z,i)$ の組は、$z=x+n\ge n$ なら $i$ についての (ii)、$z=x< n$ なら $i-1$ についての (ii) が含む。同じ段の 2 点は (iii) が含む。$(x,i),(z,i+1)$ について、$x\circ y=z$ となる $y$ がただ 1 つある。$y\ne x$ なら (iii) が含む。$y=x$ のとき、$x< n$ なら $z=x$ で (i) が含み、$x\ge n$ なら $z=x-n$ で、$i$ についての (ii) $\{\infty,(x,i),(x-n,i+1)\}$ が含む。lem-sts-count により $\mathrm{STS}(v)$ である。$\square$
Bose の構成で $n=1$ とすると、$Q=\mathbb Z/3\mathbb Z$、$x\circ y=2(x+y)$ で、$x\ne y$ なら $x\circ y$ は第 3 の元である。$\mathrm{STS}(9)$ の 12 個の三重は、縦の 3 つ $\{(x,0),(x,1),(x,2)\}$ と、$i=0,1,2$ のそれぞれについて
$$
\{(0,i),(1,i),(2,i+1)\},\quad\{(0,i),(2,i),(1,i+1)\},\quad\{(1,i),(2,i),(0,i+1)\}
$$
である。各点を含む三重は $4=(9-1)/2$ 個ある。Skolem の構成で $n=1$ とすると、$Q=\mathbb Z/2\mathbb Z$、$0\circ0=1\circ1=0$、$0\circ1=1$ で、$\mathrm{STS}(7)$ の 7 個の三重
$$
\{(0,0),(0,1),(0,2)\},\quad\{\infty,(1,i),(0,i+1)\},\quad\{(0,i),(1,i),(1,i+1)\}\qquad(i=0,1,2)
$$
を得る。Fano平面 の定理「Fano 平面の一意性」により、これは Fano 平面と同型である。位数 $13$ は Skolem の構成の $n=2$、位数 $15$ は Bose の構成の $n=2$ で得られる。
部分系と倍化
$(X,\mathcal B)$ を Steiner三重系とする。$W\subseteq X$ が、$W$ の相異なる 2 点を含む三重がいつも $W$ に含まれるという性質をもつとき、$W$ に含まれる三重の全体は $W$ 上の三重系になる。これを部分系という。どの三重もそれだけで位数 $3$ の部分系であり、後で述べる倍化の構成では、もとの三重系が部分系として現れる。
$\mathrm{STS}(v)$ が位数 $w$ の部分系 $W$ を $W\ne X$ としてもつなら、$v\ge2w+1$ である。
$x\in X\setminus W$ をとる。各 $y\in W$ について、$x,y$ を含む三重 $\{x,y,z_y\}$ がただ 1 つある。$z_y\in W$ なら、この三重は $W$ の 2 点 $y,z_y$ を含むので $W$ に含まれ、$x\in W$ となって矛盾する。よって $z_y\notin W$ であり、$z_y\ne x$ である。$y\ne y'$ なら $z_y\ne z_{y'}$ である（$z_y=z_{y'}$ なら、$x$ と $z_y$ を含む三重が二つになる）。したがって $X$ は、$W$ の $w$ 点、$x$、$w$ 個の相異なる $z_y$ を含み、$v\ge2w+1$ である。$\square$
等号の場合は次の倍化の構成で実現される。$v+1$ 個の点の上の完全グラフの辺を、互いに交わらない辺の組（1 因子）$v$ 個に分けたものを 1 因子分解という。
$\mathrm{STS}(v)$ があれば、それを部分系にもつ $\mathrm{STS}(2v+1)$ がある。
要点：新しい $v+1$ 点の上の 1 因子分解を作り、各 1 因子を古い点の一つに割り当てて、古い点と辺を合わせた三重を加える。
詳しい証明を開く
$v=1$ なら $\mathrm{STS}(3)$ が条件を満たすので、$v\ge3$（$v$ は奇数）とする。1 因子分解。$Y:=\mathbb Z/v\mathbb Z\cup\{\infty\}$（$v+1$ 点）とし、$k\in\mathbb Z/v\mathbb Z$ について $F_k:=\{\{\infty,k\}\}\cup\{\{k-j,k+j\}\mid 1\le j\le (v-1)/2\}$ とおく。$v$ は奇数なので $k\pm j$（$1\le j\le(v-1)/2$）と $k$ は相異なり、$F_k$ は $Y$ の 1 因子である。$Y$ の 2 点 $a,b\in\mathbb Z/v\mathbb Z$ を結ぶ辺は、$a+b=2k$ となる $k$ がただ 1 つある（$2$ は可逆）ので、ちょうど一つの $F_k$ に入る。$\{\infty,a\}$ は $F_a$ だけに入る。
三重系。$(X,\mathcal B)$ を $\mathrm{STS}(v)$、$\sigma\colon X\to\mathbb Z/v\mathbb Z$ を全単射とし、$X\sqcup Y$ 上で、$\mathcal B$ の三重と、$x\in X$、$e\in F_{\sigma(x)}$ についての $\{x\}\cup e$ をとる。個数は $v(v-1)/6+v(v+1)/2=(2v+1)\cdot2v/6$ である。$X$ の 2 点は $\mathcal B$ が、$x\in X$ と $y\in Y$ は $F_{\sigma(x)}$ の $y$ を含む辺が、$Y$ の 2 点はそれらを結ぶ辺の入る $F_k$ と $x=\sigma^{-1}(k)$ が覆う。lem-sts-count により $\mathrm{STS}(2v+1)$ で、$X$ は部分系である。$\square$
たとえば Fano 平面から $\mathrm{STS}(15)$ が得られ、$7$ 点の部分系をもつ。これは prop-sts-subsystem の等号 $15=2\cdot7+1$ の場合である。倍化と cor-sts-product だけでは、$1$ から始めても $13$ は得られない（$13$ は素数で、$13=2\cdot6+1$ の $6$ は位数にならない）。存在定理には Skolem の構成のような直接の構成が要る。
反例の表
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| Bose の構成で準群の位数が奇数 | 位数 $2n$ の冪等な可換準群（存在しない） | 構成に使う準群がとれること（lem-sts-quasigroups の 1 を偶数に広げること） |
| Steiner準群の (Sq3) | $\mathbb Z/5\mathbb Z$ 上の $x\circ y=3(x+y)$（(Sq1)・(Sq2) は満たす） | thm-sts-squag の 2 で三重系が得られること |
| lem-sts-count の個数 $b=v(v-1)/6$ | $X=\{1,2,3,4\}$ の 3 元部分集合 4 つすべて | すべての組を覆う族が三重系であること |
1 行目：$m=2n$ 次の冪等な可換準群があったとすると、各元 $a$ は九九の表にちょうど $m$ 回現れる。表は対称なので、対角の外では $a$ は $(x,y)$ と $(y,x)$ の対で偶数回現れ、対角の個数 $m-(\text{偶数})$ は偶数である。冪等なら対角に各元がちょうど 1 回現れるので矛盾する。2 行目：$3=2^{-1}$ なので $x\circ y$ は「中点」で、冪等かつ可換である。しかし $0\circ1=3$、$0\circ3=4\ne1$ で (Sq3) が成り立たない。$\{0,1,0\circ1\}=\{0,1,3\}$ はどの 2 点の積も第 3 の点になるわけではなく、prf-sts-squag の議論は使えない。実際 $\mathbb Z/5\mathbb Z$ の位数 $5$ は $6$ を法として $5$ なので、$\mathrm{STS}(5)$ は存在しない。3 行目：どの 2 点も 2 つの三重に含まれ、個数 $4$ は $v(v-1)/6=2$ と異なる（$v=4$ の三重系はない）。
関連項目
- 前提: Steiner系, ラテン方陣
- 例: Fano平面
- 比較: 組合せデザイン
- 発展: Kirkmanの女学生問題
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
