2017-12-08

セメレディの定理の組合せ論的証明ー３

弱正則化補題の証明. $\mathbf{V}, \mathbf{W}, \varepsilon, \mathbf{E}$ を主張の通りにとる。 $\mathbf{V}$ または $\mathbf{W}$ が空集合のときは自明に成立するので、ともに空集合ではないと仮定する。正整数 $V, W$ を用いて $\mathbf{V}=[V], \mathbf{W}=[W]$ となっているときに証明すれば十分である( $\#\mathbf{V}=V, \#\mathbf{W}=W$ とすれば、全単射 $\mathbf{V} \simeq [V], \mathbf{W} \simeq [W]$ があるため)。

$V\times W$ 行列 $(\mathbf{1}_{\mathbf{E}}(v, w) )_{(v, w) \in \mathbf{V}\times \mathbf{W}}$ の特異値分解を考えることによって、正整数 $n$ , 実数値 $\lambda_1 \geq \cdots \geq \lambda_n \geq 0$ , 関数 $f_1, \dots, f_n\colon [V] \to \mathbb{R}$ であって

$\displaystyle \frac{1}{V}\sum_{v \in [V]}f_i(v)f_j(v) = \delta_{i, j}, \quad ({}^{\forall}i, j \in [n])$

を満たすのもの(直交関係式。 $\delta_{i, j}$ はKroneckerのデルタ)、関数 $g_1, \dots, g_n\colon [W] \to \mathbb{R}$ であって

$\displaystyle \frac{1}{W}\sum_{w \in [W]}g_i(w)g_j(w) = \delta_{i, j}, \quad ({}^{\forall}i, j \in [n])$

を満たすのものが存在して、

$\displaystyle \mathbf{1}_{\mathbf{E}}(v, w) = \sum_{i=1}^n\lambda_if_i(v)g_i(w), \quad ({}^{\forall}v \in [V], w \in [W])$ −①

と書くことができる。これを二乗して $v \in [V], w \in [W]$ で平均化すると、直交関係式によってFrobeniusノルム恒等式

$\displaystyle \frac{1}{VW}\sum_{v \in [V]}\sum_{w \in [W]}\mathbf{1}_{\mathbf{E}}(v, w) = \sum_{i=1}^n\lambda_i^2$

が得られる。左辺は $1$ 以下なので、

$\displaystyle \sum_{i=1}^n\lambda_i^2 \leq 1$ −②

がわかる。これより、 $i \geq \frac{16}{\varepsilon^2}$ ならば $\lambda_i \leq \frac{\varepsilon}{4}$ が成り立つ。理由: $i \geq \frac{16}{\varepsilon^2}$ かつ $\lambda_i > \frac{\varepsilon}{4}$ なる $i$ が存在したと仮定すると、 $\{\lambda_{j}\}$ の単調減少性から

$\displaystyle \sum_{j=1}^n\lambda_{j}^2 \geq i\lambda_i^2 > \frac{16}{\varepsilon^2}\times \frac{\varepsilon^2}{16} = 1$

となって②に矛盾する。 $\lambda_i > \frac{\varepsilon}{4}$ なる $i$ を考える。①に $g_i(w)$ をかけて $w \in [W]$ で平均化すると、任意の $v \in [V]$ に対して

$\displaystyle \frac{1}{W}\sum_{w \in [W]}\mathbf{1}_{\mathbf{E}}(v, w)g_i(w) = \frac{1}{W}\sum_{w \in [W]}\sum_{j=1}^n\lambda_jf_j(v)g_j(w)g_i(w) = \lambda_if_i(v)$ −③

が得られる。 $\frac{1}{W}\sum_{w \in [W]}g_i(w)^2=1$ とCauchy-Schwarzの不等式より

$\displaystyle \frac{1}{W}\sum_{w \in [W]}\mathbf{1}_{\mathbf{E}}(v, w)g_i(w) \leq \sqrt{\left(\frac{1}{W}\sum_{w \in [W]}\mathbf{1}_{\mathbf{E}}(v, w)\right) \left(\frac{1}{W}\sum_{w \in [W]}g_i(w)^2\right)} \leq 1$

なので、③より $f_i(v) < \frac{4}{\varepsilon}$ が従う。同じことを $g_i(w) \mapsto -g_i(w)$ として考えることによって、 $\lambda_i > \frac{\varepsilon}{4}$ なる $i$ に対して $\left|f_i(v)\right| < \frac{4}{\varepsilon}, ({}^{\forall}v \in [V])$ が成り立つことがわかった。同様にして、 $\lambda_i > \frac{\varepsilon}{4}$ なる $i$ に対して $\left|g_i(w)\right| < \frac{4}{\varepsilon}, ({}^{\forall}w \in [W])$ が成り立つこともわかる。

ここで、開区間 $(-\frac{4}{\varepsilon}, \frac{4}{\varepsilon})$ を

$\displaystyle \left(-\frac{4}{\varepsilon}, \frac{4}{\varepsilon}\right) = \bigsqcup_{j=1}^{\left\lceil\frac{128}{\varepsilon^3}\right\rceil}I(\varepsilon, j)$

と分割する。ただし、 $I(\varepsilon, j)$ は区間であって長さが $\frac{\varepsilon^2}{16}$ 以下であるようなものとする( $\frac{\varepsilon^2}{16}\times \frac{128}{\varepsilon^3} = \frac{8}{\varepsilon}$ )。 $\lambda_i > \frac{\varepsilon}{4}$ なる各 $i$ について(高々 $\frac{16}{\varepsilon^2}$ 個しかないのであった)、 $j$ 毎に $f_i(v) \in I(\varepsilon, j)$ となるような $v$ 全体からなる $[V]$ の部分集合を考えることによって、 $[V]$ を高々 $\left\lceil\frac{128}{\varepsilon^3}\right\rceil$ 個の集合であって $f_i(v)$ の値が各集合上で高々 $\frac{\varepsilon^2}{16}$ しか変動しないようなものによって分割することができることがわかる。そうして、 $i$ を動かして細分をとることによって、

$\displaystyle [V]=\mathbf{V}_1 \sqcup \cdots \sqcup \mathbf{V}_A, \quad \mathbf{V}_a \neq \emptyset \ ({}^{\forall}a \in [A])$

なる分割であって、 $A \leq \left\lceil\frac{128}{\varepsilon^3}\right\rceil^{\frac{16}{\varepsilon^2}}$ かつ、任意の $a \in [A]$ に対して $\lambda_i > \frac{\varepsilon}{4}$ なる各 $i$ について $f_i$ の値が $\mathbf{V}_a$ 上高々 $\frac{\varepsilon^2}{16}$ しか変動しないような分割をとれることがわかった。

同様にして、

$\displaystyle [W]=\mathbf{W}_1 \sqcup \cdots \sqcup \mathbf{W}_B, \quad \mathbf{W}_b \neq \emptyset \ ({}^{\forall}b \in [B])$

なる分割であって、 $B \leq \left\lceil\frac{128}{\varepsilon^3}\right\rceil^{\frac{16}{\varepsilon^2}}$ かつ、任意の $b \in [B]$ に対して $\lambda_i > \frac{\varepsilon}{4}$ なる各 $i$ について $g_i$ の値が $\mathbf{W}_b$ 上高々 $\frac{\varepsilon^2}{16}$ しか変動しないような分割をとれることがわかる。

上述の分割を一つずつとって固定する。 $a \in [A], b \in [B]$ に対して

$\displaystyle d_{a, b} := \frac{1}{\#\mathbf{V}_a \cdot \#\mathbf{W}_b}\sum_{v \in \mathbf{V}_a}\sum_{w \in \mathbf{W}_b}\mathbf{1}_{\mathbf{E}}(v, w)$

と $d_{a, b}$ を定義する。このとき、定義から明らかに $0 \leq d_{a, b} \leq 1$ であり、関数 $(v, w) \mapsto \mathbf{1}_{\mathbf{E}}(v, w)-d_{a, b}$ は $\mathbf{V}_a \times \mathbf{W}_b$ 上で平均をとると $0$ である。 $\mathbf{F} \subset [V], \mathbf{G} \subset [W]$ を任意にとる。このとき、

$\begin{align} &\#\{(\mathbf{F}\times \mathbf{G}) \cap \mathbf{E}\} - \sum_{a \in [A]}\sum_{b \in [B]}d_{a, b}\#\{\mathbf{F} \cap \mathbf{V}_a\}\cdot \#\{\mathbf{G} \cap \mathbf{W}_b\} \\ &= \sum_{a \in [A]}\sum_{b \in [B]}\sum_{v \in \mathbf{V}_a}\sum_{w \in \mathbf{W}_b}\mathbf{1}_{\mathbf{F}}(v)\mathbf{1}_{\mathbf{G}}(w)\left( \mathbf{1}_{\mathbf{E}}(v, w)-d_{a, b}\right)\end{align}$ −④

と書くことができる。ここで、各 $a \in [A], b \in [B]$ に対して $\alpha_a, \beta_b$ を

$\displaystyle \alpha_a := \frac{1}{\#\mathbf{V}_a}\sum_{v \in \mathbf{V}_a}\mathbf{1}_{\mathbf{F}}(v), \quad \beta_b := \frac{1}{\#W_b}\sum_{w \in \mathbf{W}_b}\mathbf{1}_{\mathbf{G}}(w)$

と導入する。そうして、

$\displaystyle \mathbf{1}_{\mathbf{F}}(v)\mathbf{1}_{\mathbf{G}}(w) = (\mathbf{1}_{\mathbf{F}}(v)-\alpha_a)\mathbf{1}_{\mathbf{G}}(w) + \alpha_a(\mathbf{1}_{\mathbf{G}}(w)-\beta_b)+\alpha_a\beta_b$

と分解して④に代入すると、 $\alpha_a\beta_b$ のところは $\mathbf{V}_a\times \mathbf{W}_b$ 上の平均をとると消えるので、④の左辺の絶対値は三角不等式によって

$\displaystyle \left|\sum_{a \in [A]}\sum_{b \in [B]}\sum_{v \in \mathbf{V}_a}\sum_{w \in \mathbf{W}_b}(\mathbf{1}_{\mathbf{F}}(v)-\alpha_a)\mathbf{1}_{\mathbf{G}}(w)\left(\mathbf{1}_{\mathbf{E}}(v, w)-d_{a, b}\right) \right|$ −⑤

と

$\displaystyle \left|\sum_{a \in [A]}\sum_{b \in [B]}\sum_{v \in \mathbf{V}_a}\sum_{w \in \mathbf{W}_b}\alpha_a(\mathbf{1}_{\mathbf{G}}(w)-\beta_b)\left(\mathbf{1}_{\mathbf{E}}(v, w)-d_{a, b}\right) \right|$ −⑥

で押さえることができる。あとはそれぞれを評価すればよろしい。

⑤の評価: $\alpha_a$ の定義より $\mathbf{1}_{\mathbf{F}}(v)-\alpha_a$ の $\mathbf{V}_a$ 上の平均が $0$ なので、 $d_{a, b}$ の項は消えて

を評価すればよく、 $v \in [V], w \in [W]$ に対して

$\begin{align} F(v) &:= \sum_{a \in [A]}(\mathbf{1}_{\mathbf{F}}(v) - \alpha_a)\mathbf{1}_{\mathbf{V}_a}(v) \\ G(w) &:= \sum_{b \in [B]}\mathbf{1}_{\mathbf{G}}(w)\mathbf{1}_{\mathbf{W}_b}(w) = \mathbf{1}_{\mathbf{G}}(w)\end{align}$

と $F(v), G(w)$ を導入すれば(分割をとっているので和の項で非零になり得るのは一項だけであることに注意)、これは

$\displaystyle \left|\sum_{v \in [V]}\sum_{w \in [W]}F(v)G(w)\mathbf{1}_{\mathbf{E}}(v, w)\right|$

と書くことができる。①を使えば

$\displaystyle \left|\sum_{i=1}^n\lambda_i\left(\sum_{v \in [V]}F(v)f_i(v)\right)\left(\sum_{w \in [W]}G(w)g_i(w)\right)\right|$ −⑦

と書き直せる。 $\{\frac{f_i(v)}{\sqrt{V}}\}_{v \in [V]}$ は正規直交系をなしているので、Besselの不等式と $F(v)$ の絶対値が $1$ 以下であることから

$\displaystyle \sum_{i=1}^n\left|\frac{1}{V}\sum_{v \in [V]}F(v)f_i(v)\right|^2 \leq \frac{1}{V}\sum_{v \in [V]}F(v)^2 \leq 1$

と評価できる。同様に

$\displaystyle \sum_{i=1}^n\left|\frac{1}{W}\sum_{w \in [W]}G(w)g_i(w)\right|^2 \leq 1$

が成り立つ。よって、Cauchy-Schwarzの不等式より

$\begin{align} &\left|\sum_{i\colon \lambda_i \leq \frac{\varepsilon}{4}}\lambda_i\left(\sum_{v \in [V]}F(v)f_i(v)\right)\left(\sum_{w \in [W]}G(w)g_i(w)\right)\right| \\ &\leq \frac{\varepsilon}{4}\left|\sum_{i\colon \lambda_i \leq \frac{\varepsilon}{4}}\left(\sum_{v \in [V]}F(v)f_i(v)\right)\left(\sum_{w \in [W]}G(w)g_i(w)\right)\right| \\ &\leq \frac{\varepsilon}{4}\sqrt{\sum_{i=1}^n\left(\sum_{v \in [V]}F(v)f_i(v)\right)^2}\sqrt{\sum_{i=1}^n\left(\sum_{w \in [W]}G(w)g_i(w)\right)^2} \\ &\leq \frac{\varepsilon}{4}VW\end{align}$ −⑧

と評価できる。 $\lambda_i > \frac{\varepsilon}{4}$ であれば $f_i(v)$ の値は各 $\mathbf{V}_a$ 上で高々 $\frac{\varepsilon^2}{16}$ しか変動しないので、 $v \in \mathbf{V}_a$ に対して $f_i(v) = e_{i,a}+f_{i, a}(v), \ 0 \leq f_{i, a}(v) \leq \frac{\varepsilon^2}{16}$ と書ける。 $F(v)$ は定義より $\mathbf{V}_a$ 上の平均が $0$ なので

$\displaystyle \sum_{v \in [V]}F(v)f_i(v) = \sum_{a \in [A]}\sum_{v \in \mathbf{V}_a}F(v)\left(e_{i,a}+f_{i, a}(v)\right) = \sum_{a \in [A]}\sum_{v \in \mathbf{V}_a}F(v)f_{i, a}(v)$

と変形でき、 $F(v)$ の絶対値が $1$ 以下なので、三角不等式より

$\displaystyle \left|\sum_{v \in [V]}F(v)f_i(v) \right| \leq \frac{\varepsilon^2}{16}V$

が成り立つ。また、 $G(w)$ の絶対が $1$ 以下なので、直交関係式とCauchy-Schwarzの不等式より

$\displaystyle \left|\sum_{w \in [W]}G(w)g_i(w)\right| \leq \sqrt{\sum_{w \in [W]}G(w)^2}\sqrt{\sum_{w \in [W]}g_i(w)^2} \leq W$

である。②より

$\displaystyle 1 \geq \sum_{i=1}^n\lambda_i^2 \geq \sum_{i\colon \lambda_i > \frac{\varepsilon}{4}}\lambda_i^2 > \frac{\varepsilon}{4}\sum_{i\colon \lambda_i > \frac{\varepsilon}{4}}\lambda_i$

なので、

$\displaystyle \sum_{i\colon \lambda_i > \frac{\varepsilon}{4}}\lambda_i < \frac{4}{\varepsilon}$

が成り立ち、

$\displaystyle \left|\sum_{i\colon \lambda_i > \frac{\varepsilon}{4}}\lambda_i\left(\sum_{v \in [V]}F(v)f_i(v)\right)\left(\sum_{w \in [W]}G(w)g_i(w)\right)\right| \leq \frac{\varepsilon^2}{16}VW\sum_{i\colon \lambda_i > \frac{\varepsilon}{4}}\lambda_i < \frac{\varepsilon}{4}VW$

と評価できる。よって、⑧と合わせると、⑦(従って⑤)は $\frac{\varepsilon}{2}VW$ で上から押さえられることが示された。

⑥の評価: $\beta_b$ の定義より $\mathbf{1}_{\mathbf{G}}(w)-\beta_b$ の $\mathbf{W}_b$ 上の平均が $0$ なので、 $d_{a, b}$ の項は消えて

$\displaystyle \left|\sum_{a \in [A]}\sum_{b \in [B]}\sum_{v \in \mathbf{V}_a}\sum_{w \in \mathbf{W}_b}\alpha_a(\mathbf{1}_{\mathbf{G}}(w)-\beta_b)\mathbf{1}_{\mathbf{E}}(v, w)\right|$

を評価すればよく、 $v \in [V], w \in [W]$ に対して

$\begin{align} F(v) &:= \sum_{a \in [A]}\alpha_a\mathbf{1}_{\mathbf{V}_a}(v) \\ G(w) &:= \sum_{b \in [B]}(\mathbf{1}_{\mathbf{G}}(w)-\beta_b)\mathbf{1}_{\mathbf{W}_b}(w)\end{align}$

と $F(v), G(w)$ を導入すれば(⑤の評価と同じ記号であるが定義し直している)、これは

$\displaystyle \left|\sum_{v \in [V]}\sum_{w \in [W]}F(v)G(w)\mathbf{1}_{\mathbf{E}}(v, w)\right|$

と書くことができる。①を使えば

$\displaystyle \left|\sum_{i=1}^n\lambda_i\left(\sum_{v \in [V]}F(v)f_i(v)\right)\left(\sum_{w \in [W]}G(w)g_i(w)\right)\right|$ −⑨

と書き直せる。⑤の評価のときと同様に

$\displaystyle \left|\sum_{i\colon \lambda_i \leq \frac{\varepsilon}{4}}\lambda_i\left(\sum_{v \in [V]}F(v)f_i(v)\right)\left(\sum_{w \in [W]}G(w)g_i(w)\right)\right| \leq \frac{\varepsilon}{4}VW$ −⑩

と評価できる。 $\lambda_i > \frac{\varepsilon}{4}$ であれば $g_i(w)$ の値は各 $\mathbf{W}_b$ 上で高々 $\frac{\varepsilon^2}{16}$ しか変動しないので、 $w \in \mathbf{W}_b$ に対して $g_i(w) = e_{i,b}+g_{i, b}(w), \ 0 \leq g_{i, b}(w) \leq \frac{\varepsilon^2}{16}$ と書ける。 $G(w)$ は定義より $\mathbf{W}_b$ 上の平均が $0$ なので

$\displaystyle \sum_{w \in [W]}G(w)g_i(w) = \sum_{b \in [B]}\sum_{w \in \mathbf{W}_b}G(w)\left(e_{i,b}+g_{i, b}(w)\right) = \sum_{b \in [B]}\sum_{w \in \mathbf{W}_b}G(w)g_{i, b}(w)$