Fisherの不等式

同義語:Fisher's inequalityFisher inequalityフィッシャーの不等式

概要

Fisherの不等式(Fisher's inequality)とは、$v$ 個の点の集合の $k$ 元部分集合(ブロック)の族で、$k< v$ かつ相異なる 2 点がちょうど $\lambda\ge1$ 個のブロックに含まれるもの(2-デザイン)では、ブロックの個数 $b$ が $b\ge v$ を満たすという定理である。接続行列 $N$ について $NN^{\mathsf T}$ が正定値になることから、$N$ の行の 1 次独立性として証明される。等号の場合が対称デザインで、Fano 平面はその例である。ブロックの大きさをそろえない形や、部分集合どうしの交わりの大きさだけを仮定する形にも一般化される。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: Steiner系, 行列の階数

Fisher の不等式(Fisher's inequality)とは、$v$ 個の点の集合から $k$ 個ずつのブロックを選び、どの 2 点もちょうど $\lambda\ge1$ 個のブロックに含まれるようにした配置(2-デザイン)では、$k< v$ である限り、ブロックの個数 $b$ が点の個数 $v$ を下回らない、という定理である。
$$ b\ge v $$
たとえば $7$ 点の Fano平面 は $b=v=7$ で等号が成り立つ。ブロックを少なくしようとしても点の個数より減らせないという主張であり、組合せ論の問いが、接続行列の行が 1 次独立であるという線形代数の事実に帰着する典型例である。統計学者 R. A. Fisher が 1940 年に示した(Sta13 §12.4)。同じ Fisher の名をもつ Fisherの正確検定 とは別の主題である。
この記事では、接続行列の計算からこの不等式を証明し、等号の場合、割り算の条件だけでは見えない配置の非存在、集合の交わりの大きさだけを仮定する非一様な形、ブロックが平行類に分かれる場合の強い形を述べる。

定義

2-デザイン

$v,k,\lambda$ を $2\le k< v$、$\lambda\ge1$ を満たす整数とする。$v$ 個の元の集合 $X$(点の集合)と、$X$ の $k$ 元部分集合の族 $\mathcal B$(ブロックの族。同じ部分集合が重複して現れてもよい)の組 $(X,\mathcal B)$ が、次を満たすとき 2-$(v,k,\lambda)$ デザイン、または釣り合い型不完備ブロック計画(balanced incomplete block design、BIBD)という。

  • $X$ の相異なる 2 点は、ちょうど $\lambda$ 個のブロックに含まれる。
    ブロックの個数を $b$ と書く(重複は重複の数だけ数える)。

$k< v$ が「不完備」の意味である。$\lambda=1$ の場合が Steiner系 $S(2,k,v)$ であり、一般の $t$-デザインは 組合せデザイン で扱う。
点 $p\in X$ を含むブロックの個数を数えると、次のようにパラメータの関係が得られる。

パラメータの関係

2-$(v,k,\lambda)$ デザインでは、どの点もちょうど $r$ 個のブロックに含まれ、
$$ r(k-1)=\lambda(v-1),\qquad bk=vr $$
が成り立つ。とくに $r>\lambda$ である。

2 通りに数える

点 $p$ を固定し、点 $q\neq p$ とブロック $B$ の組で $p,q\in B$ となるものの個数を数える。$q$ を先に選ぶと $(v-1)\lambda$ 個である。$B$ を先に選ぶと、$p$ を含むブロックの個数を $r_p$ として $r_p(k-1)$ 個である。よって $r_p=\lambda(v-1)/(k-1)$ は $p$ によらない。これを $r$ とおく。$k< v$ から $k-1< v-1$ なので $r>\lambda$ である。
点とブロックの組で点がブロックに含まれるものを数えると、点から数えて $vr$、ブロックから数えて $bk$ である。$\square$

接続行列

点に $p_1,\dots,p_v$、ブロックに $B_1,\dots,B_b$ と番号を付ける。$p_i\in B_j$ のとき $1$、そうでないとき $0$ を $(i,j)$ 成分とする $v\times b$ 実行列 $N$ を、$(X,\mathcal B)$ の接続行列という。

$NN^{\mathsf T}$ の $(i,i')$ 成分は、$p_i$ と $p_{i'}$ をともに含むブロックの個数である。したがって、$I$ を単位行列、$J$ を成分がすべて $1$ の $v$ 次正方行列として
$$ NN^{\mathsf T}=(r-\lambda)I+\lambda J $$
が成り立つ。対角成分は $r$、非対角成分は $\lambda$ である。

主定理

Fisher の不等式

2-$(v,k,\lambda)$ デザインのブロックの個数 $b$ は $b\ge v$ を満たす。さらに、$\operatorname{rank}N=v$ であり、prop-fisher-parameters の $r$ について $r\ge k$ である。

行が 1 次独立であること

$x\in\mathbb{R}^v$ について
$$ \|N^{\mathsf T}x\|^2=x^{\mathsf T}NN^{\mathsf T}x=(r-\lambda)\sum_{i=1}^vx_i^2+\lambda\Bigl(\sum_{i=1}^vx_i\Bigr)^2 $$
である。prop-fisher-parameters により $r-\lambda>0$ であり、$\lambda>0$ なので、$x\neq0$ なら右辺は正である。よって $N^{\mathsf T}x=0$ なら $x=0$ であり、$N^{\mathsf T}$ は単射である。すなわち $N$ の $v$ 本の行は $\mathbb{R}^b$ の中で 1 次独立である。したがって $\operatorname{rank}N=v$ であり、$\mathbb{R}^b$ の次元と比べて $v\le b$ を得る。最後に、$bk=vr$ と $b\ge v$ から $r\ge k$ である。$\square$

$NN^{\mathsf T}$ は 正定値行列 である、というのが証明の中身である。$J$ の固有値は $v$(1 重)と $0$($v-1$ 重)なので、$NN^{\mathsf T}$ の固有値は $r-\lambda+\lambda v=rk$(1 重)と $r-\lambda$($v-1$ 重)であり、行列式 $\det(NN^{\mathsf T})=rk(r-\lambda)^{v-1}$ が正であることからも階数が分かる。
直観としては、$v$ 個の点を、それぞれを含むブロックの集合と同一視する。2 点はどれも同じ大きさ $\lambda$ だけ重なり、自分自身とはそれより大きい $r$ だけ重なる。内積がこの形になるベクトルは 1 次独立であり、$b$ 次元の空間に $b$ 本より多くは入らない。

等号の場合と例

等号 $b=v$ が成り立つデザインを対称デザインという(組合せデザイン の定義「対称デザイン」)。$bk=vr$ から、対称デザインであることは $r=k$ と同値であり、$r(k-1)=\lambda(v-1)$ と合わせると $k(k-1)=\lambda(v-1)$ である。対称デザインでは相異なる 2 つのブロックがちょうど $\lambda$ 点で交わる(組合せデザイン の定理「対称デザインのブロックの交わり」)。同じ定理により、点とブロックの役割を入れ替えた配置も対称な 2-$(v,k,\lambda)$ デザインである。

Fano 平面の接続行列

$X=\{1,\dots,7\}$、ブロック $\{1,2,4\},\{2,3,5\},\{3,4,6\},\{4,5,7\},\{5,6,1\},\{6,7,2\},\{7,1,3\}$ は 2-$(7,3,1)$ デザインである(Steiner系 の例「Fano 平面」)。$r=3$、$b=7$ で等号が成り立つ。接続行列は
$$ N=\begin{pmatrix} 1&0&0&0&1&0&1\\ 1&1&0&0&0&1&0\\ 0&1&1&0&0&0&1\\ 1&0&1&1&0&0&0\\ 0&1&0&1&1&0&0\\ 0&0&1&0&1&1&0\\ 0&0&0&1&0&1&1 \end{pmatrix} $$
で、どの 2 行も内積が $1$、各行の長さの 2 乗が $3$ である。よって $NN^{\mathsf T}=2I+J$ であり、どの 2 列も内積が $1$ であること(2 つのブロックが 1 点で交わること)も確かめられる。

次の表は小さいデザインの例である。$r$、$b$ は prop-fisher-parameters から決まる。

$(v,k,\lambda)$$r$$b$$b$ と $v$例
$(7,3,1)$$3$$7$$b=v$Fano平面
$(7,4,2)$$4$$7$$b=v$Fano 平面のブロックの補集合
$(11,5,2)$$5$$11$$b=v$$\{1,3,4,5,9\}$ の $\mathbb{Z}/11\mathbb{Z}$ の平行移動
$(13,4,1)$$4$$13$$b=v$$\{0,1,3,9\}$ の $\mathbb{Z}/13\mathbb{Z}$ の平行移動(位数 $3$ の 射影平面)
$(5,4,3)$$4$$5$$b=v$$5$ 点の $4$ 元部分集合すべて
$(9,3,1)$$4$$12$$b>v$$\mathbb{F}_3^2$ の直線
$(15,3,1)$$7$$35$$b>v$Kirkmanの女学生問題 の配置
割り算の条件では除けないパラメータ

$(v,k,\lambda)=(16,6,1)$ を考える。prop-fisher-parameters の式から $r=15/5=3$、$b=16\cdot3/6=8$ で、どちらも整数である。つまり $r$、$b$ が整数になるという条件は満たされる。しかし $b=8< 16=v$ なので、thm-fisher-main により 2-$(16,6,1)$ デザイン、すなわち Steiner 系 $S(2,6,16)$ は存在しない。
直接にも確かめられる。ブロック $B$ を 1 つとると、$B$ の $6$ 点のそれぞれを通る $B$ 以外のブロックは $r-1=2$ 個ずつあり、$\lambda=1$ からこれらは互いに異なる。よって $b\ge1+6\cdot2=13>8$ であり、矛盾する。

$\lambda=1$ のときは、線形代数を使わない数え上げでも不等式が示せる。$\lambda\ge2$ では同じ議論が働かないところに、接続行列を使う意味がある。

$\lambda=1$ の場合の数え上げ

$\lambda=1$ とする。$k< v$ なので、点 $p$ とそれを含まないブロック $B$ がある。$B$ の各点 $q$ について、$p,q$ を含むブロックはただ 1 つある。$q\neq q'$ に対してこの 2 つのブロックが同じなら、そのブロックは $q,q'$ を含むので $B$ に等しくなり、$p\notin B$ に反する。よって $p$ を含むブロックは $k$ 個以上あり、$r\ge k$ である。$bk=vr$ から $b\ge v$ を得る。
$\lambda\ge2$ では、1 つのブロックが $p$ と $B$ の 2 点を含むことがあるので、この議論はそのままでは働かない。

対称デザインのパラメータには、さらに強い制約がある。たとえば $v$ が偶数なら $k-\lambda$ は平方数である(組合せデザイン の定理「$v$ が偶数の対称デザイン」)。

非一様な形

ブロックの大きさをそろえなくても、同じ計算が働く。点とブロックの役割を入れ替えて述べると、次のようになる(Sta13 Theorem 12.4)。

非一様な Fisher の不等式

$n\ge1$ とし、$C_1,\dots,C_m$ を $n$ 元集合 $Y$ の相異なる部分集合とする。ある整数 $\lambda\ge1$ について、すべての $i\neq j$ で $\lvert C_i\cap C_j\rvert=\lambda$ ならば、$m\le n$ である。

$m\ge2$ としてよい。
ある $\lvert C_i\rvert=\lambda$ の場合。 $j\neq i$ について $\lvert C_i\cap C_j\rvert=\lvert C_i\rvert$ なので $C_i\subset C_j$ であり、相異なるので $C_j\setminus C_i\neq\emptyset$ である。$j\neq l$(ともに $i$ と異なる)なら $C_j\cap C_l$ は $C_i$ を含み大きさ $\lambda$ なので $C_i$ に等しく、$C_j\setminus C_i$ と $C_l\setminus C_i$ は交わらない。よって $m-1\le\lvert Y\setminus C_i\rvert=n-\lambda\le n-1$ である。
すべての $\lvert C_i\rvert>\lambda$ の場合。 $\gamma_i:=\lvert C_i\rvert-\lambda>0$ とおく。$C_i$ の特性ベクトルを行とする $m\times n$ 行列を $M$ とすると、$x\in\mathbb{R}^m$ について
$$ \|M^{\mathsf T}x\|^2=\lambda\Bigl(\sum_ix_i\Bigr)^2+\sum_i\gamma_ix_i^2 $$
であり、$x\neq0$ なら正である。よって $M^{\mathsf T}$ は単射で、$m\le n$ である。$\square$

$\lvert C_i\cap C_j\rvert$ が $0$ でもよいとすると、この結論は成り立たない(下の表)。

大きさのそろわないブロック

有限集合 $X$($\lvert X\rvert=v\ge2$)の部分集合の族 $\mathcal B$(同じ部分集合が重複してもよく、個数は重複込みで数える)が、次の 2 条件を満たすとする。(i) 相異なる 2 点はちょうど $\lambda\ge1$ 個のブロックに含まれる。(ii) 相異なる 2 点 $p,q$ に対し、一方だけを含むブロックがある。このとき $\lvert\mathcal B\rvert\ge v$ である。

ブロックの番号の集合を $Y$ とする。$p\in X$ に、$p$ を含むブロックの番号の集合 $C_p\subset Y$ を対応させる。(ii) から $C_p$ は相異なり、(i) から $\lvert C_p\cap C_q\rvert=\lambda$ である。(i) から $\lvert Y\rvert\ge\lambda\ge1$ なので、thm-fisher-nonuniform から $v\le\lvert Y\rvert$ である。$\square$

2-デザインは $r>\lambda$ により (ii) を満たす($C_p=C_q$ なら $r=\lvert C_p\cap C_q\rvert=\lambda$ となる)ので、これは thm-fisher-main の不等式を含む。

点と直線の配置

有限集合 $X$($v\ge2$ 点)の、$2$ 点以上からなる部分集合の族(「直線」)で、相異なる 2 点がちょうど 1 本の直線に含まれ、$X$ 自身は直線でないものを考える。相異なる $p,q$ が (ii) を満たさないとすると、$p,q$ を含む直線を $L$ として、$p$ を通る直線は $q$ も通るので $L$ だけである。$X\setminus L$ の点 $z$ をとると($X\neq L$)、$p,z$ を含む直線は $L$ でなければならず、$z\notin L$ に反する。よって cor-fisher-pairwise から、直線の本数は $v$ 以上である。
平面の有限個の点で、全部が 1 直線上にはないときに、それらを結ぶ直線が $v$ 本以上あるという事実(Sylvester–Gallaiの定理 の系「結ぶ直線の本数」)は、その特別な場合である。上の議論は幾何を使わない。

平行類に分かれるデザイン

2-デザインのブロックの族が、それぞれ $X$ を分割するような部分族(平行類)に分かれるとき、デザインは分解可能であるという。各点はどの平行類でもちょうど 1 つのブロックに含まれるので、平行類の個数は $r$ である。

分解可能なデザインの下界

分解可能な 2-$(v,k,\lambda)$ デザインでは $b\ge v+r-1$ である。

$N$ の列を平行類ごとにまとめる。平行類 $\Pi_1,\dots,\Pi_r$ のそれぞれについて、$\Pi_l$ に属する列の和は成分がすべて $1$ のベクトルである。よって、$l=2,\dots,r$ について「$\Pi_l$ の列の和から $\Pi_1$ の列の和を引くと $0$」という $r-1$ 個の 1 次関係があり、これらは 1 次独立である(各関係は、$\Pi_l$ の列の係数を、その関係だけが非零にもつ)。したがって $\operatorname{rank}N\le b-(r-1)$ である。thm-fisher-main の $\operatorname{rank}N=v$ から $v\le b-r+1$ を得る。$\square$

分解可能なデザインの数値

$\mathbb{F}_3^2$ の $9$ 点と $12$ 本の直線は、$r=4$ の分解可能な 2-$(9,3,1)$ デザインである(方向ごとに平行類をなす)。$b=12=9+4-1$ で、prop-fisher-resolvable の等号が成り立つ。Kirkmanの女学生問題 の配置は分解可能な 2-$(15,3,1)$ デザインで、$b=35$、$v+r-1=21$ である。

体を取り替えると

prf-fisher-main は実数の 2 乗が $0$ 以上であることを使っている。正の標数の体では、接続行列の階数は $v$ より小さくなることがある。

Fano 平面の $\mathbb{F}_2$ の上の階数

ex-fisher-fano の $N$ を $\mathbb{F}_2$ の行列とみると、$NN^{\mathsf T}=2I+J\equiv J\pmod 2$ であり、$\operatorname{rank}_{\mathbb{F}_2}N=4$ である(行基本変形による有限の計算で確かめられる)。$N$ の行で張られる $\mathbb{F}_2^7$ の部分空間は、座標の並べ替えを除いて長さ $7$ の Hamming符号 である。したがって、行が 1 次独立であることは $\mathbb{F}_2$ の上では成り立たない。

一般に、$\det(NN^{\mathsf T})=rk(r-\lambda)^{v-1}$ を割り切らない素数 $p$ については、$N$ の $\mathbb{F}_p$ の上の階数も $v$ である。Fano 平面では $rk(r-\lambda)^{v-1}=9\cdot2^6$ なので例外になりうるのは $p=2,3$ だけで、実際 $\mathbb{F}_3$ の上の階数は $6$ である(有限の計算)。

反例:仮定を外すと成り立たないこと

次の表の各行では、条件を 1 つだけ替えて、結論が成り立たなくなることを示す。

替える条件反例成り立たなくなること
def-fisher-design の $k< v$($k=v$ にする)$X=\{1,\dots,5\}$、$\mathcal B=\{X\}$($\lambda=1$)$b\ge v$:$b=1< 5$
def-fisher-design の $\lambda\ge1$($\lambda=0$ にする)$k=2$、$v=3$、$\mathcal B$ は空の族$b\ge v$:$b=0< 3$
「ちょうど $\lambda$ 個」(少なくとも $1$ 個にする)$X=\{1,\dots,6\}$、$\{1,2,3,4\},\{1,2,5,6\},\{3,4,5,6\}$$b\ge v$:$b=3< 6$
「2 点」(1 点にする:どの点も同じ個数のブロックに含まれる)$X=\{1,\dots,6\}$、$\{1,2,3\},\{4,5,6\}$$b\ge v$:$b=2< 6$
thm-fisher-nonuniform の $\lambda\ge1$($\lambda=0$ にする)$Y=\{1,\dots,n\}$、$\emptyset,\{1\},\dots,\{n\}$$m\le n$:$m=n+1$
thm-fisher-nonuniform の「相異なる」(同じ集合を許す)$Y=\{1\}$、$C_1=C_2=\{1\}$($\lambda=1$)$m\le n$:$m=2$
cor-fisher-pairwise の (ii)$\mathcal B=\{X\}$($\lambda=1$、$v\ge2$)$\lvert\mathcal B\rvert\ge v$:$\lvert\mathcal B\rvert=1$

3 行目で、各ブロックは 3 組 $\{1,2\},\{3,4\},\{5,6\}$ のうちの 2 組の和であり、どの 2 組も 1 つのブロックに含まれるので、どの 2 点も少なくとも 1 つのブロックに含まれる。一方、$\{1,2\}$ は $2$ 個のブロックに、$\{1,3\}$ は $1$ 個のブロックに含まれる。4 行目のブロックは、どの点も $1$ 個のブロックに含まれるが、$1$ と $4$ をともに含むブロックはない。

補足

  • 歴史:Fisher は 1940 年に $b\ge v$ を示し、Bose が 1949 年にこれを一般化した(Sta13 §12.4)。thm-fisher-nonuniform は、その一般化を点とブロックの役割を入れ替えて述べた形である(同所)。
  • 線形代数の方法:集合の族の個数を、対応するベクトルが 1 次独立であることから抑える考え方は、極値集合論で広く使われる。極値集合論 も参照。
  • 対称デザインの存在:等号の場合にどのパラメータが実現されるかは、Fisher の不等式だけでは分からない。Hadamard行列 から作られる対称デザインの例がある。

関連項目

参考文献

[1]
Richard P. Stanley, Algebraic Combinatorics: Walks, Trees, Tableaux, and More, Undergraduate Texts in Mathematics, Springer, 2013, §12.4 The nonuniform Fisher inequality(BIBD の定義と関係式、Fisher(1940)の $b\ge v$、Bose(1949)の一般化、Theorem 12.4 とその証明)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する