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)$

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

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

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

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

である。②より

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

が成り立つので、

と評価できる。よって、⑩と合わせると、⑨(従って⑥)は $\frac{\varepsilon}{2}VW$ で上から押さえられる。

二つの評価を合わせることによって、④の左辺は $\varepsilon VW$ で上から押さえられることが示された。 Q.E.D.

2017-12-04

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

等間隔に並ぶ素数を追い求めて

弱正則化補題 (Frieze, Kannan) $\mathbf{V}, \mathbf{W}$ を有限集合とし、 $\varepsilon > 0$ および $\mathbf{E} \subset \mathbf{V} \times \mathbf{W}$ をとる。このとき、 $A, B=O_{\varepsilon}(1)$ , $a \in [A], b \in [B]$ 毎に $0 \leq d_{a, b} \leq 1$ , 分割

$\begin{align} \mathbf{V} &= \mathbf{V}_1 \sqcup \cdots \sqcup \mathbf{V}_A \\ \mathbf{W} &= \mathbf{W}_1 \sqcup \cdots \sqcup \mathbf{W}_B\end{align}$

が存在して、任意の $\mathbf{F} \subset \mathbf{V}, \mathbf{G} \subset \mathbf{W}$ に対して

$\displaystyle \left| \#\{(\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\}\right| \leq \varepsilon \#\mathbf{V}\cdot \#\mathbf{W}$

が成り立つ。

これは次の記事で証明する。ここでは、後で使う系を導出する。

系 $\mathbf{V}, \mathbf{W}$ を有限集合とし、 $\varepsilon > 0$ および $w \in \mathbf{W}$ 毎に $\mathbf{E}_w \subset \mathbf{V}$ をとる。このとき、 $A=O_{\varepsilon}(1)$ , $a \in [A], w \in \mathbf{W}$ 毎に $0 \leq c_{a, w} \leq 1$ , 分割

$\displaystyle \mathbf{V} = \mathbf{V}_1 \sqcup \cdots \sqcup \mathbf{V}_A$

が存在して、任意の $\mathbf{F} \subset \mathbf{V}$ に対して

$\displaystyle \left| \#\{\mathbf{F} \cap \mathbf{E}_w\} - \sum_{a \in [A]}c_{a, w}\#\{\mathbf{F}\cap \mathbf{V}_a\}\right| \leq \varepsilon \#\mathbf{V}$

が高々 $\varepsilon \#\mathbf{W}$ 個の $w \in \mathbf{W}$ を除いて成立する。

証明. $\mathbf{E}:=\{(v, w) \in \mathbf{V} \times \mathbf{W} \mid v \in \mathbf{E}_w \}$ とし、 $\varepsilon \mapsto \varepsilon^2/2$ として弱正則化補題を適用する。すると、 $A, B=O_{\varepsilon}(1)$ , $a \in [A], b \in [B]$ 毎に $0 \leq d_{a, b} \leq 1$ , 分割

$\begin{align} \mathbf{V} &= \mathbf{V}_1 \sqcup \cdots \sqcup \mathbf{V}_A \\ \mathbf{W} &= \mathbf{W}_1 \sqcup \cdots \sqcup \mathbf{W}_B\end{align}$

が存在して、任意の $\mathbf{F} \subset \mathbf{V}, \mathbf{G} \subset \mathbf{W}$ に対して

が成り立つ。 $a \in [A], b \in [B], w \in \mathbf{W}_b$ のとき $c_{a, w}:=d_{a, b}$ と定義する。 $\mathbf{E}$ の定義から

$\displaystyle \#\{(\mathbf{F}\times \mathbf{G}) \cap \mathbf{E}\} = \sum_{w \in \mathbf{G}}\#\{\mathbf{F} \cap \mathbf{E}_w\}$

が成り立ち、 $a \in [A]$ に対して

$\displaystyle \sum_{b \in [B]}d_{a, b}\#\{\mathbf{F} \cap \mathbf{V}_a\}\cdot \#\{\mathbf{G} \cap \mathbf{W}_b\} = \sum_{w \in \mathbf{G}}c_{a, w}\#\{\mathbf{F} \cap \mathbf{V}_a\}$

が成り立つので、

$\displaystyle \left|\sum_{w \in \mathbf{G}}\left(\#\{\mathbf{F} \cap \mathbf{E}_w\}-\sum_{a \in [A]}c_{a, w}\#\{\mathbf{F} \cap \mathbf{V}_a\}\right) \right| \leq \frac{\varepsilon^2}{2}\#\mathbf{V} \cdot \#\mathbf{W}$

と書き直すことができる。これを、 $\mathbf{G}$ として

$\begin{align} \mathbf{G}^{+} &:= \left\{w \in \mathbf{W} \ \left| \ \#\{\mathbf{F} \cap \mathbf{E}_w\}-\sum_{a \in [A]}c_{a, w}\#\{\mathbf{F} \cap \mathbf{V}_a\} > 0 \right\}\right. \\ \mathbf{G}^{-} &:= \left\{w \in \mathbf{W} \ \left| \ \#\{\mathbf{F} \cap \mathbf{E}_w\}-\sum_{a \in [A]}c_{a, w}\#\{\mathbf{F} \cap \mathbf{V}_a\} < 0 \right\}\right. \end{align}$

のそれぞれに適用して足し合わせると

$\displaystyle \sum_{w \in \mathbf{W}}\left|\#\{\mathbf{F} \cap \mathbf{E}_w\}-\sum_{a \in [A]}c_{a, w}\#\{\mathbf{F} \cap \mathbf{V}_a\} \right| \leq \varepsilon^2\#\mathbf{V} \cdot \#\mathbf{W}$

を得る。

$\begin{align} &\varepsilon \#\mathbf{V} \cdot \#\left\{ w \in \mathbf{W} \ \left| \ \left|\#\{\mathbf{F} \cap \mathbf{E}_w\}-\sum_{a \in [A]}c_{a, w}\#\{\mathbf{F} \cap \mathbf{V}_a\} \right| \geq \varepsilon \#\mathbf{V}\right\} \right. \\ &= \sum_{w \in \mathbf{W}}\varepsilon\#\mathbf{V} \cdot \mathbf{1}_{\left\{ w \in \mathbf{W} \ \left| \ \left|\#\{\mathbf{F} \cap \mathbf{E}_w\}-\sum_{a \in [A]}c_{a, w}\#\{\mathbf{F} \cap \mathbf{V}_a\} \right| \geq \varepsilon \#\mathbf{V}\right\} \right.}(w)\\ &\leq \sum_{w \in \mathbf{W}}\left|\#\{\mathbf{F} \cap \mathbf{E}_w\}-\sum_{a \in [A]}c_{a, w}\#\{\mathbf{F} \cap \mathbf{V}_a\} \right| \leq \varepsilon^2\#\mathbf{V} \cdot \#\mathbf{W}\end{align}$

と不等式評価できるので

$\begin{align} &\#\left\{ w \in \mathbf{W} \ \left| \ \left|\#\{\mathbf{F} \cap \mathbf{E}_w\}-\sum_{a \in [A]}c_{a, w}\#\{\mathbf{F} \cap \mathbf{V}_a\} \right| \leq \varepsilon \#\mathbf{V}\right\} \right. \\ &\geq \#\left\{ w \in \mathbf{W} \ \left| \ \left|\#\{\mathbf{F} \cap \mathbf{E}_w\}-\sum_{a \in [A]}c_{a, w}\#\{\mathbf{F} \cap \mathbf{V}_a\} \right| < \varepsilon \#\mathbf{V}\right\} \right. \geq (1-\varepsilon) \#\mathbf{W}\end{align}$

が得られ、これが主張していたことであった。 Q.E.D.

最後の不等式評価はMarkovの不等式およびその証明そのものである。今後は同じ変形は省略する。

2017-12-02

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

等間隔に並ぶ素数を追い求めて

Szemerédiの定理の証明は既に当ブログで解説済みです：

integers.hatenablog.com

しかしながら、Szemerédiの定理の証明は異なる分野の数学を用いて複数得られており、その中でも組合せ論的議論により証明したSzemerédiによるオリジナル証明に興味がありました。

その証明が簡単でないことを色々なところで目にしますが、Terence Taoが"Szemerédi's proof of Szemerédi's theorem"という、Szemerédiによるオリジナル証明を簡略化できるところは簡略化してまとめたunpublished noteを書いています。原論文ではなくこちらの方を勉強して当ブログに日本語で記録しておこうと思います(複数記事使います)。

記号設定

$\mathbb{N}=\{1, 2, 3, \dots \}$ .
$[N]:=\{1, 2, \dots, N\}$ for $N \in \mathbb{N}$ . ただし、便宜的に $[0]:=\emptyset$ とする。
$K \in \mathbb{N}$ に対して、 $K$ -APを $a \in \mathbb{Z}, r \in \mathbb{N}$ で

$\displaystyle \overrightarrow{P{ }} = a+r\cdot \overrightarrow{[K]}:=(a+kr)_{k \in [K]}=(a+r, a+2r, \dots, a+Kr)$

と表すことのできる組として定義する(ad hoc)。つまり、必ず単調増加に並べて考える。 $r=1$ のときは $a+\overrightarrow{[K]}$ , $a=0$ かつ $r=1$ のときは $\overrightarrow{[K]}$ と書く。
$K$ -AP: $\overrightarrow{P{ }}=a+r\cdot \overrightarrow{[K]}$ に対して、 $P \colon \mathbb{Z} \to \mathbb{Z}$ を $P(k):=a+kr$ と定義する。 $\overrightarrow{P{ }}=(P(1), \dots, P(K) )$ となっている。
$K$ -AP: $\overrightarrow{P{ }}=a+r\cdot \overrightarrow{[K]}$ が集合 $\mathbf{A}$ に含まれるとは $P([K]) \subset \mathbf{A}$ が成り立つときにいう。
$\overrightarrow{P{ }}$ がAPであるとは、或る $K \in \mathbb{N}$ が存在して $K$ -APであるときにいう(ad hoc)。このとき、 $\mathrm{len}(\overrightarrow{P{ }}):=K$ を $\overrightarrow{P{ }}$ の長さという。
AP全体のなす集合を $\mathcal{AP}$ とする。
集合 $\mathbf{E} \subset \mathbb{Z}$ と $h \in \mathbb{Z}$ に対して、 $h+\mathbf{E}:=\{h+n \mid n \in \mathbf{E}\}$ .
$X=O(Y)$ は或る絶対定数 $C$ に対して $\left|X\right| \leq CY$ が成り立つことの略記法。 $C$ がパラメータ依存するときは、例えば $k$ に依存するならば、 $X=O_k(Y)$ のように表す。
集合 $\mathbf{X}$ に対して、 $\mathbf{1}_{\mathbf{X}}$ は $\mathbf{X}$ の特性関数。つまり、 $x \in \mathbf{X}$ なら $\mathbf{1}_{\mathbf{X}}(x) = 1$ で、 $x \not \in \mathbf{X}$ であれば $\mathbf{1}_{\mathbf{X}}(x) = 0.$

Banach上漸近密度

$\mathbf{A} \subset \mathbb{Z}$ のBanch上漸近密度 $\overline{bd}(\mathbf{A})$ を

$\displaystyle \overline{bd}(\mathbf{A}) := \limsup_{N \to \infty}\max_{h \in \mathbb{Z}}\frac{\#\{\mathbf{A} \cap (h+[N])\}}{N}$

と定義する。

一般に、 $\overline{d}(\mathbf{A}) \leq \overline{bd}(\mathbf{A})$ が成り立つ( $\overline{d}(\mathbf{A})$ は $\mathbf{A}$ の上漸近密度)。

$\displaystyle \mathbf{A}:=\bigcup_{n \in \mathbb{N}}([n^3, n^3+n] \cap \mathbb{Z})$ とする。このとき、 $\overline{d}(\mathbf{A})=0$ であるが、 $\overline{bd}(\mathbf{A})=1$ である。

Szemerédiの定理

次の定理を証明するのが目的である。

定理 (Szemerédi, 1975)
$\mathbf{A} \subset \mathbb{N}$ が $\overline{bd}(\mathbf{A}) > 0$ を満たせば、 $\mathbf{A}$ は任意の $K \in \mathbb{N}$ に対して $K$ -APを含む。

integers.hatenablog.com

の無限版Szemerédiの定理と同値であることを証明しておく。

証明. 上漸近密度の不等式関係から、上記定理から無限版Szemerédiの定理が従う。無限版Szemerédiの定理が成り立つと仮定すると既に証明しているように有限版Szemerédiの定理(上記記事参照)が成り立つ。 $\mathbf{A} \subset \mathbb{N}$ を $\overline{bd}(\mathbf{A}) = \delta > 0$ を満たすような集合とする。正整数 $k$ を任意にとる。このとき、Banach上漸近密度の定義より