外書輪講I(第10回)

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

HPに行く

今回はMiniature 17を行いました。

Miniature 17
この話は、16と同じような手法を用いるという点で、少し16と似ています。

最初に、極値集合論一般論について書いてありますが、それは省略します。
もし、輪講などで話すときには、この部分を忠実に訳して説明する必要は特になく、
もし話すとしても、手早くまとめて、本題に入るとよいと思います。

定理を述べておきます。
もし、ある、結果を話す場合には、必ず、定理の主張を黒板に書いて
ください。そして、証明を始めましょう。

定理
$X$ を $n$ 個の頂点からなる集合とします。$p$ を素数として、$X$ の中の
$2p-1$ 個の点集合からなる部分集合族を $\mathcal{F}$ とおきます。
ここで、$\mathcal{F}$ の中のどの２つの部分集合族を取っても
その共通部分は、$p-1$ 個ではない場合、$\mathcal{F}$ の要素の数は、
$$|\mathcal{F}|\le \binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{p-1}$$
という不等式を満たす。


まず、$\mathcal{F}$ の中に入る元は、高々、$\binom{n}{2p-1}$ くらいという
ことになりますが、以下説明するように、定理の主張最後の不等式の右辺は
それほど大きくはありません。
つまり、$p-1$ 個の点を共通部分を持つような集合族がないとすれば、
そのような集合族は、それほど多くはないということを意味しています。
(この条件は、$2p-1$ 個の中の $p-1$ 点は、丁度半分くらいの点の数ですから
話も表題(Midium-Size Intersection Is Hard To Avoid)にあるとおりですね。)
さらにそれを数値的に表しているのが、次の系です。


系
$n=4p$ とする。$\mathcal{F}$ を上の定理と同じものとします。
このとき、
$$\frac{\binom{4p}{2p-1}}{|\mathcal{F}|}\le 1.1^n$$
が成り立つ。

$\binom{4p}{2p-1}$ の中で、$|\mathcal{F}|$ の比率は、$1/1.1^n$くらいですから
それほどでもないと思うかもしれませんが、
$p=2$ のときは、0.46、$p=3$ のときは、0.31
$p=5$ のときは、0.14、$p=7$ のときは、0.07
$p=11$ のときは、0.02...
となり、極端に小さくなっていきます。
つまり、$p$ が大きくなっていけば、必ず、どこかの共通部分に
$p-1$ 点となるようなものが増えていくということになります。
(これはどういうことなのでしょうか？)

系の証明は不等式処理だけなので、このブログではスキップします。

今、$\{0,1\}^n$ 上の ${\mathbb F}_p$ に値をもつ関数全体を $V$ とし、$\mathcal{F}\subset \{0,1\}^n$ 上の関数全体を
$V_\mathcal{F}$ とします。
これらは、体 ${\mathbb F}_p$ 上のベクトル空間となります。


定理の証明をしましょう。

$A\in \mathcal{F}$ とします。
このとき、$A$ に対して、${\mathbb F}^n_p$ を
もし、$A\subset \{1,\cdots, n\}$ が $2p-1$ 個の点集合のとき、
特性ベクトル $c_A\in {\mathbb F}_2^n$ を以下のように定義します。
$c_A=(a_1,\cdots, a_n)$ と書いた時、
$i\in A$ なら、$a_i=1$ で、そうでない場合、$a_i=0$ とします。

$A\in \mathcal{F}$ に対して $f_A\in V_\mathcal{F}$ を以下のような関数とします。
$$f_A(x)=\prod_{s=0}^{p-2}(\sum_{x_i\in A}x_i-s)$$
前回(Miniature 16)で登場した関数 $f$ にほどよく似ていますね。
Miniature 16 ではさらに、$\prod_{s=0}^{p-1}(1-x_s)$ のようなものを引いていますが、今回はありません。

ここで、${\mathbb F}_p$ が体であるので、$ab=0$ ならば、$a=0$ もしくは、$b=0$ である
ことに注意しておきます。
$B\in \mathcal{F}$ に対して、$(b_1,\cdots, b_n)=c_B$ としたとき、
また、$\sum_{i\in A}b_i=|A\cap B|$ であることにも注意しておきます。

今、$f_A(c_B)\neq 0\bmod p$ とすると、$0\le \forall s\le p-2$ に対して、
$|A\cap B|\not\equiv  s\bmod p$ となります。よって、$|A\cap B|\equiv p-1\bmod p$
となり、条件から、$A=B$ でなければなりません。

逆に、$f_A(c_A)=\prod_{s=0}^{p-2}(|A|-s)$ の各項は、$0$ ではならいので、全て掛け合わせても $0$ にはなりません。
よって、$f_A(c_A)\not\equiv 0\bmod p$ となります。

つまり、以下の同値関係が成り立ったことになります。

$$f_A(c_B)\equiv 0\bmod p\Leftrightarrow A\neq B$$

この関数 $\{f_A|A\in \mathcal{F}\}$ のその双対ベクトル(正確にはその定数倍)は、
$V_{\mathcal{F}}$ で一次独立となります。
よって、$|\mathcal{F}|$ の個数は、$V$ の中の  $\{f_A|A\in \mathcal{F}\}$
で張られるベクトル空間 $V_\mathcal{F}$ の次元と考えれば、
$V_{\mathcal{F}}$ がどのようなベクトルの部分空間となるかを
考えればよいことになります。

$V_\mathcal{F}$ の次元を評価します。
$f(x)$ は $\{0,1\}^n$ 上の、${\mathbb F}_p^n$ に値をもつ多項式で、
$x_i^2=x_i$ であることから、

$f_A(x)$ の単項式には、2次の因子を除くことができます。
よって、$f_A(x)$ の形は、$\{1,2,\cdots, n\}$ の部分集合だけあり、
最大 $p-1$ 個だけ選んでいるので、

$$\dim(V_\mathcal{F})\le \binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{p-1}$$
が成り立ちます。