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

定理 (混合補題) $\mathcal{P}\subset \mathcal{AP}$ を非有界で二重カウンティング性質を満たすものとし、 $\mathbf{A} \subset \mathbb{Z}$ は $\mathcal{P}$ に沿った密度をもち、 $d_{\mathcal{P}}(\mathbf{A})=\delta$ であるとする。任意の $\varepsilon > 0$ に対して $N_1(\varepsilon) \in \mathbb{N}$ が存在し、 $\varepsilon$ と任意の整数 $N \geq N_1(\varepsilon)$ に対して $N_2(\varepsilon, N) \geq N$ が存在して、 $N_1(\varepsilon) \leq L \leq N_2(\varepsilon, L) \leq H$ なる $L, H\in \mathbb{N}$ をとり、 $L \times H$ -長方形 $\overrightarrow{R{ }}$ であって任意の $l \in [L]$ に対して $\overrightarrow{R^l} \in \mathcal{P}$ なるものをとるとき、次が成立する:
(i) (単混合) $\mathbf{E} \subset [H]$ に対して $l \in [L]$ が存在して

$\#\{h \in \mathbf{E} \mid R(l, h) \in \mathbf{A}\} \geq \delta\#\mathbf{E}-\varepsilon H$

が成り立つ。
(ii) (多重混合) $A\leq C_{\varepsilon}$ を満たす $A \in \mathbb{N}$ と、 $\mathbf{E}_1, \dots, \mathbf{E}_A \subset [H]$ に対して $l \in [L]$ が存在して

$\left|\#\{h \in \mathbf{E}_a \mid R(l, h) \in \mathbf{A}\}-\delta \#\mathbf{E}_a\right| \leq \varepsilon H$

が任意の $a \in [A]$ に対して成り立つ。ただし、 $C_{\varepsilon}$ は記事２の系の $A=O_{\varepsilon}(1)$ で $\varepsilon \mapsto \frac{\varepsilon}{3}$ としたときの定数*1。
(iii) (高次多重混合) 有限集合 $\mathbf{W}$ で添字付けられる、集合 $\mathbf{E}_w \subset [H]$ からなる族 $\{\mathbf{E}_w\}_{w \in \mathbf{W}}$ に対して $l \in [L]$ が存在して

$\left|\#\{h \in \mathbf{E}_w \mid R(l, h) \in \mathbf{A}\}-\delta \#\mathbf{E}_w\right| \leq \varepsilon H$

が高々 $\varepsilon \#\mathbf{W}$ 個の例外を除く $w \in \mathbf{W}$ に対して成立する。

(ii)の証明にvan der Waerdenの定理を用い、(iii)の証明に弱正則化補題(の系)を用いる。 $N_1, N_2$ は(i)〜(iii)で共通ではなく、証明中では $N_1^{(\mathrm{i})}$ のように表す。van der Waerdenの定理によって存在する $N(k, m)$ を $N_{\mathrm{vdW}}(k, m)$ と表す。

証明. (i)の証明: $N_1^{(\mathrm{i})}(\varepsilon)$ は記事４の命題の $N_1(\varepsilon/2)$ および記事４の③の $\varepsilon/2$ に対する $N$ 以上であるとし、 $N_2^{(\mathrm{ii})}(\varepsilon, N)$ は記事４の命題の $N_2(\varepsilon/2, N)$ 以上であるとする。すると、記事４の命題の(ii)より、高々 $\frac{\varepsilon}{2}H$ 個の例外を除く $h \in [H]$ に対して $\overrightarrow{R_h} \in \mathcal{P}$ が成り立つ。このような $h \in [H]$ に対して記事４の③より

$\displaystyle \mu_{\overrightarrow{R_h}}(\mathbf{A}) \geq \delta-\frac{\varepsilon}{2}$

が成り立つ。このとき、

$\displaystyle \#\{h \in \mathbf{E} \mid \overrightarrow{R_h} \not \in \mathcal{P}\} \leq \#\{h \in [H]\mid \overrightarrow{R_h} \not \in \mathcal{P}\} \leq \frac{\varepsilon}{2}H$

より

$\begin{align} \sum_{l \in [L]}\#\{h \in \mathbf{E} \mid R(l, h) \in \mathbf{A}\}&=\sum_{l \in [L]}\sum_{h \in \mathbf{E}}\mathbf{1}_{\mathbf{A}}(R(l, h) )＝\sum_{h \in \mathbf{E}}\sum_{l \in [L]}\mathbf{1}_{\mathbf{A}}(R(l, h) )\\ &\geq \sum_{h \in \mathbf{E}, \ \overrightarrow{R_h} \in \mathcal{P}}\mu_{\overrightarrow{R_h}}(\mathbf{A})L \geq \left(\#\mathbf{E}-\frac{\varepsilon}{2}H\right)\left(\delta-\frac{\varepsilon}{2}\right)L \\ &\geq \delta L\#\mathbf{E}-\varepsilon LH\end{align}$

と評価できる。よって、鳩ノ巣原理により或る $l \in [L]$ が存在して

$\#\{h \in \mathbf{E} \mid R(l, h) \in \mathbf{A}\} \geq \delta\#\mathbf{E}-\varepsilon H$

が成り立つ。

(ii)の証明: $L':=N_1^{(\mathrm{i})}(\varepsilon/2) \geq N_1^{(\mathrm{i})}(\varepsilon)$ として、 $N_1^{(\mathrm{ii})}(\varepsilon) \geq N_{\mathrm{vdW}}(L', 3^{C_{\varepsilon}}) \geq N_{\mathrm{vdW}}(L', 3^{A})$ および $N_2^{(\mathrm{ii})}(\varepsilon, N) \geq \max\{N_2^{(\mathrm{i})}(\varepsilon/2, L'), N, N(\varepsilon/2)\} \geq N_2^{(\mathrm{i})}(\varepsilon, L')$ を満たすように $N_1^{(\mathrm{ii})}, N_2^{(\mathrm{ii})}$ をとる(ただし、 $N(\varepsilon/2)$ は記事４の③のもの)。

$[L]$ の $3^A$ 色塗り分け $c\colon [L] \to \{-1, 0, +1\}^A$ を各 $l \in [L]$ に対して $c(l) = (c_a(l) )_{a \in [A]}$ と表して、

$\#\{h \in \mathbf{E}_a \mid R(l, h) \in \mathbf{A}\} < \delta \#\mathbf{E}_a-\varepsilon H$

なら $c_a(l):=-1$ ,

$\#\{h \in \mathbf{E}_a \mid R(l, h) \in \mathbf{A}\} > \delta \#\mathbf{E}_a+\varepsilon H$

なら $c_a(l):=+1$ ,

$\left|\#\{h \in \mathbf{E}_a \mid R(l, h) \in \mathbf{A}\}-\delta \#\mathbf{E}_a\right| \leq \varepsilon H$

なら $c_a(l)=0$ と定義する。

van der Waerdenの定理より、 $[L]$ に含まれる或る $L'$ -AP $\overrightarrow{Q{ }}$ および色 $c = (c_a)_{a \in [A]} \in \{-1, 0, +1\}^A$ が存在して、任意の $l' \in [L']$ に対して $c(Q(l') ) = c$ が成り立つ。

$c_a=-1$ なる $a \in [A]$ が存在したと仮定する。このとき、任意の $l' \in [L']$ に対して

$\#\{h \in \mathbf{E}_a \mid R(Q(l'), h) \in \mathbf{A}\} < \delta \#\mathbf{E}_a-\varepsilon H$

が成り立つ。これは、 $\mathbf{E} \mapsto \mathbf{E}_a$ として $L'\times H$ -長方形 $(R(Q(l'), h) )_{(l', h) \in [L'] \times [H]}$ に対する(i)の主張に矛盾する( $\overrightarrow{Q{ }}$ がAPであるから長方形となることに注意)。

$c_a=+1$ なる $a \in [A]$ が存在したと仮定する。このとき、任意の $l' \in [L']$ に対して

$\#\{h \in \mathbf{E}_a \mid R(Q(l'), h) \in \mathbf{A}\} > \delta \#\mathbf{E}_a+\varepsilon H$

が成り立つ。また、 $\overrightarrow{R^{Q(l')}} \in \mathcal{P}$ は長さ $H$ なので、記事４の③より

$\displaystyle \#\{h \in [H] \mid R(Q(l'), h) \in \mathbf{A}\} \leq \delta H+\frac{\varepsilon}{2}H$

である。よって、

$\displaystyle \#\{h \in [H]\setminus \mathbf{E}_a \mid R(Q(l'), h) \in \mathbf{A}\} < \delta(H-\#\mathbf{E}_a)-\frac{\varepsilon}{2}H$

なので、 $\mathbf{E} \mapsto [H]\setminus \mathbf{E}_a, \ \varepsilon \mapsto \frac{\varepsilon}{2}$ として $L'\times H$ -長方形 $(R(Q(l'), h) )_{(l', h) \in [L'] \times [H]}$ に対する(i)の主張にやはり矛盾する。

従って、任意の $a \in [A]$ に対して $c_a=0$ が示された。 $l$ としては例えば $Q(1)$ を選べる。

(iii)の証明: $N_1^{(\mathrm{iii})}(\varepsilon) \geq N_1^{(\mathrm{ii})}(\frac{\varepsilon}{3C_{\varepsilon}})$ および $N_2^{(\mathrm{iii})}(\varepsilon, N) \geq N_2^{(\mathrm{ii})}(\frac{\varepsilon}{3C_{\varepsilon}}, N)$ を満たすように $N_1^{(\mathrm{iii})}, N_2^{(\mathrm{iii})}$ をとる。

弱正則化補題の系より、或る $A\leq C_{\varepsilon}$ と分割

$[H]=\mathbf{V}_1 \sqcup \cdots \sqcup \mathbf{V}_A,$

$a \in [A], w \in \mathbf{W}$ 毎に $0 \leq c_{a, w} \leq 1$ が存在して、任意の $\mathbf{C} \subset [H]$ に対して

$\displaystyle \left| \#\{\mathbf{C} \cap \mathbf{E}_w\} - \sum_{a \in [A]}c_{a, w}\#\{\mathbf{C} \cap \mathbf{V}_a\}\right| \leq \frac{\varepsilon}{3}H$ –①

が高々 $\frac{\varepsilon}{3}\#\mathbf{W}$ 個の例外を除く $w \in \mathbf{W}$ に対して成立する。

$\mathbf{E}_a \mapsto \mathbf{V}_a$ として(ii)を使うと、或る $l \in [L]$ が存在して

$\displaystyle \left|\#\{h \in \mathbf{V}_a \mid R(l, h) \in \mathbf{A}\}-\delta \#\mathbf{V}_a\right| \leq \frac{\varepsilon}{3A}H$ –②

が任意の $a \in [A]$ に対して成り立つ。 $\mathbf{C}=\{h \in [H] \mid R(l, h) \in \mathbf{A}\}$ とすると①は

$\displaystyle \left|\#\{h \in \mathbf{E}_w \mid R(l, h) \in \mathbf{A} \}-\sum_{a \in [A]}c_{a, w}\#\{h \in \mathbf{V}_a \mid R(l, h) \in \mathbf{A}\}\right| \leq \frac{\varepsilon}{3}H$ –③

となるので、②、③より

$\begin{align} &\left|\#\{h \in \mathbf{E}_w \mid R(l, h) \in \mathbf{A}\}-\delta \sum_{a \in [A]}c_{a, w}\#\mathbf{V}_a\right| \\ &\leq \left|\#\{h \in \mathbf{E}_w \mid R(l, h) \in \mathbf{A}\}-\sum_{a \in [A]}c_{a, w}\#\{h \in \mathbf{V}_a \mid R(l, h) \in \mathbf{A}\}\right|\\ &\quad +\sum_{a \in [A]}c_{a, w}\left|\#\{h \in \mathbf{E}_w \mid R(l, h) \in \mathbf{A} \}-\delta \#\mathbf{V}_a\right| \\ &\leq \frac{\varepsilon}{3}H+\sum_{a \in [A]}c_{a, w}\frac{\varepsilon}{3A}H \leq \frac{2\varepsilon}{3}H \end{align}$ –④

が高々 $\frac{\varepsilon}{3}\#\mathbf{W}$ 個の例外を除く $w \in \mathbf{W}$ に対して成立する。

また、 $\mathbf{C}=[H]$ とすると①は

$\displaystyle \left|\#\mathbf{E}_w-\sum_{a \in [A]}c_{a, w}\#\mathbf{V}_a\right| \leq \frac{\varepsilon}{3}H$ –⑤

となるので、④、⑤より高々 $\varepsilon \#\mathbf{W}$ 個の例外を除く $w \in \mathbf{W}$ に対して*2

$\displaystyle \left|\#\{h \in \mathbf{E}_w \mid R(l, h) \in \mathbf{A}\}-\delta \#\mathbf{E}_w \right| \leq \frac{2\varepsilon}{3}H+\delta\cdot \frac{\varepsilon}{3}H \leq \varepsilon H$