数学外書輪講I(第12回)

[場所1E501（月曜日5限）]

HPに行く
manabaに行く

今回は、

• 33-Miniature のMiniature 4
• LangのVII章

を読みました。

Ｍiniature 4 (Same-Size Intersections)

この話は、極値集合論の話です。
前回も書いたように、ある集合の中で与えられた条件を満たす部分集合の

うち、最大、最小を満たす部分集合について研究するものを

極値集合論といいました。

しかし、最後に書くように、組み合わせ論のデザイン理論の一部(の変種)でもあります。

Miniature 3で出てきた定理以下のようなものでした。

定理(Miniature 3)
$n$ 点集合の部分集合 $C_i\ \ (i=1,...,m)$ を以下のようにとる。

• $|C_i|$ は奇数
• $|C_i\cap C_j|$ は偶数

(ただし、集合の絶対値はその集合に含まれる元の個数とする。)

このとき、$m\le n$ である。

つまり、そのような $n$ 点集合の部分集合は、
重複を除いてたかだか $n$ 個しかとれないということになります。

Miniature 4でのセッティングでの定理は以下のようになります。

定理(Miniature 4)

ある $n$ 点集合の相異なる部分集合 $C_i\ \ \ (i=1,...,m)$ があったときに、

$|C_i\cap C_j|$ が一定数 $t$ であれば、$m\le n$ が成り立つ。

証明は以下のようにしてできます。

(証明の概略)

Miniature 3と同様に、$a_{ij}$  を $1$ if $j\in C_i$ かつ、$0$ if $j\not\in C_i$ として

定義して、$A=(a_{ij})$ とおくと、$A$ は $m\times n$ 行列ができる。

ある $i$ に対して $|C_i|=t$ となる場合と、任意の $i$ に対して $|C_i|>t$ となる場合と
場合分けが必要。

後者の場合は、行列 $A\cdot A^T$ を、$B$ としてその成分を $(b_{ij})$ とすると、
$B$ は $m\times m$ 行列で、$b_{ii}=|C_i|$ であり、$B_{ij}=|C_i\cap C_j|$ となり、

$m=\text{rank}(B)\le \text{rank}(A)\le n$ がいえる。


このような不等式のことをフィッシャーの不等式(Fisher’s inequality)と呼びます。
これは、組み合わせ論におけるブロックデザイン(block design)の分野の初歩に出てくる
不等式です。

ブロックデザイン
有限集合 $\mathcal{P}$ と有限集合 $\mathcal{B}$ が与えます。
$\mathcal{P}$ を点の集合とよび、$\mathcal{B}$ をブロックの集合といいます。
また、$\mathcal{P}$ と $\mathcal{B}$ に、ある関係(incidence)があり、
それを、$\mathcal{I}\subset \mathcal{P}\times \mathcal{B}$ とします。
このとき、$B\in \mathcal{B}$ が以下を満たすとき、
デザイン(もしくは、2-デザイン)といいます。
$\mathcal{P}$ の要素のことを点ということにします。

• $|\mathcal{P}|=v$
• 任意のブロック $B\in \mathcal{B}$ に対して、$(p,B)\in\mathcal{I}$ となる(incidentな)点は $k$ 個
• 任意の 2点 $x,y\in \mathcal{P}$ に対して、$x,y$ を共にincidentなブロックはちょうど $\lambda$ 個

このようなデザインを 2-$(v,k,\lambda)$ デザインといいます。

また、この3番目の条件の任意の2点を任意の相異なる $t$ 個の点

とき、$t$-$(v,k,\lambda)$-デザインといいます。

この状況の時、フィッシャーの不等式とは、$k\ge v$ を満たします。

証明は上で書いたものと同じです。

この、Same-Size Intersections にでてくる状況はいわゆるデザインではありませんが、

それに似た状況です。

$X=\{C_i\}$ とし、$B_i=\{x\in X|x\in C_i\}$ としておくと、

$C_i$ に含まれる点(ブロックに相当する)全体の数は、

一定ではありませんので、上の定義でいうデザインではありません。

Matousekの本では、

場合分けの後者の状況で、$C_i,C_j\in \mathcal{P}$ に対して、$C_i$ と $C_j$ と共通して

incidentな点全体は、$C_i\cap C_j$ に一致しますので、デザインの２番目の条件が

成り立っています。

なので、$C_i$ に入る点全体が一定数であれば、2-デザインということになります。

フィッシャーの不等式(Fisher’s inequality)自体、一つのブロックに関係する点が一定でなくても成り立ちます。これは今回の内容でした。

そういう意味で、この不等式を一般化されたフィッシャーの不等式(Generalized Fisher’s inequality)と呼んでいます。

射影平面

ブロックデザイン応用例で一番よく出てくるのは、有限射影幾何です。

有限個の点に対して射影幾何を考えることができます。

詳しくは、下の、参考文献かその文献にあたってみるとよいと思います。

射影平面の公理とは、

1. 任意の相異なる２点はただ一つの直線で結ばれる。
2. 相異なる２直線の交わりは、ただ一つの点である。
3. どの3点も一直線上にない4点が存在する。

をいいます。

射影空間を考えることもできますが、その場合は、任意の部分空間をブロックとすること

で定義ができます。

射影平面を有限集合とすると、ある自然数 $n$ に対して、

2-$(n^2+n+1,n+1,1)$-デザインになります。

この $n$ のことを射影平面の位数(order)といいます。

そもそも射影空間とは、ベクトル空間の直線全体の空間をいいます。

射影空間を有限集合として考えているので、体は有限体となりますが、

ここではもっと一般に、上の公理にあう有限集合ならばかまいません。

有限射影平面の標準的な例は、有限体 ${\mathbb F}_q$ の3次元ベクトル空間の中の

直線全体があります。これをデザルグ平面といいます。記号では

$PG(2,q)$ と書きます。

例えば、$q=2$ の場合だと、

ベクトル空間 $V={\mathbb F}_2^3$ における直線は、ゼロでないベクトル全体と

同じです。というのも、$0$ でない元でスカラー倍することは、$1$ をかけることになる

ので、$V$ 上の直線全体は、次の、７つの元

$[x,y,z]=[0,0,1], [0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1]$ と同じになります。

つまり、$|PG(2,2)|=7$ です。

また、平面上では、相異なる2直線は、一点で交わることが要請されます。

よって、$PG(2,2)$ 上の直線(ブロック)は、一つの平面を表します。

なので、平面は、$z=0,y=0,y+z=0, x=0,x+z=0,x+y=0,x+y+z=0$ の7つになります。

(ブロックデザインの定義のところで、点とブロックを入れ替えた条件がそれぞれ、

対応する個数が等しくなるとき、対称デザインといいます。

例えば、任意の点に関係するブロックは $k$ 個となる。)

このとき、一つの平面に入る直線は、3つになります。例えば、$z=0$ に入る直線は

$[1,0,0],[0,1,0],[1,1,0]$ です。

また、相異なる２直線 ($V$ 上では２平面) の交わりは、1つの点 ($V$ では1つの直線)

を定めます。

よって、$PG(2,2)$ は 2-(7,3,1)-デザインだということがわかりました。

問題は、有限射影平面は全てデザルグ的か？ということですが、じつは

そうではありません、ここでは書ききれないくらい、非デザルグ的な

射影平面が存在します。それは、下の参考文献をみてください。

(しかし、3次元以上の有限射影空間はデザルグ的であることは古くから知られている。

例えば、参考文献の２つ目をみよ)

そこでも、多くの面白い幾何学があるようです。

例えば、射影平面として実現できるorderは素べきか？

という問題がありますが、未だ解決していません。

また、以前のMotousekででてきたコーディング(error detecting codes)の話も、

このブロックデザインを使った応用もあります。コードの

文字が位数が２の有限体だったことを思い出してください。

コーディングを用いて有限射影平面へ応用することもできるようです。

参考文献

• 平峰豊, 有限射影平面概観, 数理解析研究所講究録1214(2001)46-61 (リンク)
• P. Dembowski, Finite Geometries, Springer-Verlag, Berlin, 1997. xii+375 pp. ISBN: 3-540-61786-8