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

定理 (帰納的ステップ) $K \geq 3$ とし、 $\Omega \subset [K]$ は或る $0 \leq k_0 < K$ に対して $[k_0]$ を含むが $k_0+1$ は含まないと仮定する*1。このとき、 $C'(K, \Omega)$ が成り立つならば $C(K, (\Omega\setminus [k_0]) \cup \{k_0+1\})$ が成り立つ。

帰納的ステップ $\Longrightarrow$ Szemerédiの定理の証明. $\mathrm{wt}(\Omega) := \sum_{k \in \Omega}2^{k-1}$ とすると写像 $\mathrm{wt}\colon 2^{[K]} \to [2^K-1] \cup \{0\}$ は全単射である(二進展開)。 $\mathrm{wt}(\Omega) < 2^K-1$ とすると、或る $0 \leq k_0 < K$ に対して $[k_0]$ を含むが $k_0+1$ は含まない。よって、記事９の補題と帰納的ステップにより $C(K, \Omega)$ は $C(K, (\Omega \setminus [k_0]) \cup \{k_0+1\})$ を導く。

$\mathrm{wt}( (\Omega \setminus [k_0]) \cup \{k_0+1\}) = \mathrm{wt}(\Omega)+1$

が成り立つので、 $C(K, \emptyset)$ から開始することによって任意の $\Omega \subset [K]$ に対して $C(K, \Omega)$ が成立することがわかった。特に $C(K, \{K\})$ も成立するため、記事９の補題と命題よりSzemerédiの定理が従う。 Q.E.D.

$K=3$ のときは

$C(3, \emptyset) \Longrightarrow C(3, \{1\}) \Longrightarrow C(3, \{2\}) \Longrightarrow C(3, \{1, 2\}) \Longrightarrow C(3, \{3\})$

と進行するが、実は議論を修正することによって

$C(3, \emptyset) \Longrightarrow C(3, \{2\}) \Longrightarrow C(3, \{3\})$

という進行も可能であり、この結果 $2$ -APの存在が従う。ところが、更に記事９の命題の議論も修正が可能であり、 $C(3, \{3\})$ から $3$ -APの存在性を示せる。これが記事７、記事８で実行したRothの定理の証明である。

帰納的ステップの証明でKeyとなるカウンティング補題を証明する。高次多重混合を複数回適用する。

定理 (カウンティング補題)
$K \geq 3$ とし、 $\Omega \subset [K]$ は或る $0 \leq k_0 < k$ に対して $[k_0]$ を含むが $k_0+1$ を含まないとする。 $0 < \varepsilon \leq 1$ とし、 $\mathcal{P} \subset \mathcal{AP}$ は非有界かつ二重カウンティング性質を満たすとする。 $\mathbf{S} \subset \mathbb{Z}, \mathbf{A} \subset \mathbf{S}$ は $\mathcal{P}$ に沿った密度をもち、 $d_{\mathcal{P}}(\mathbf{S}) = \sigma \geq 1-\varepsilon$ , $d_{\mathcal{P}}(\mathbf{A})=\delta, 0 < \delta \leq 1$ であるとする。 $\kappa > 0$ をとる。このとき、 $N(\varepsilon, \delta, \kappa), N'(\varepsilon, \delta, \kappa, N) \in \mathbb{N}$ が存在して次が成り立つ( $N \geq N(\varepsilon, \delta, \kappa)$ ): $L' \geq N(\varepsilon, \delta, \kappa)$ , $H \geq N'(\varepsilon, \delta, \kappa, L')$ なる $L', H \in \mathbb{N}$ をとる。 $r \in \mathbb{N}$ をとる。また、 $\overrightarrow{l'}=(l'_k)_{k \in \Omega}$ ( $l'_k \in [L']$ )で添字付けられる $K$ -APの族 $(\overrightarrow{P_{\overrightarrow{l'}}})_{\overrightarrow{l'} \in [L']^{\Omega}}$ が存在して
(i) 任意の $\overrightarrow{l'} \in [L']^{\Omega}$ と $k \in [K]$ に対して、 $H$ -AP $P_{\overrightarrow{l'}}(k)+r\cdot \overrightarrow{[H]} \in \mathcal{P}$ .
(ii) 任意の $k \in [K]$ に対して、

$\{h \in [H] \mid P_{\overrightarrow{l'}}(k)+rh \in \mathbf{A}\} \subset [H]$

は $k' \leq k$ なる $\overrightarrow{l'}$ の成分 $l'_{k'}$ にしか依存しない。
(iii) 任意の $k \in \Omega$ に対して、 $\overrightarrow{l''} \in [L']^{\Omega \setminus \{k\}}$ をとると $L'$ -AP $\overrightarrow{Q_{k, \overrightarrow{l''}}}$ が存在して、 $\Omega \setminus \{k\}$ 上では $\overrightarrow{l''}$ と成分が一致するような $\overrightarrow{l'}=(l'_{k'})_{k' \in \Omega} \in [L']^{\Omega}$ に対して $Q_{k, \overrightarrow{l''}}(l'_k) = P_{\overrightarrow{l'}}(k)$ が成り立つ。
を満たすと仮定する。 $\mathcal{Q}$ を $K$ -AP $\overrightarrow{Q{ }} \subset [H]$ の集合とする。 $k \in [K], h \in [H]$ に対して $\mathcal{Q}_k(h) \subset \mathcal{Q}$ を

$\mathcal{Q}_k(h) := \{\overrightarrow{Q{ }} \in \mathcal{Q} \mid Q(k) = h \}$

と定める。 $0 \leq k_1 \leq k_0$ なる整数をとる。
このとき、或る $\overrightarrow{l^{\ast}} \in [L']^{\Omega}$ が存在して、任意の $k' \in [K] \setminus [k_1]$ に対して

$\displaystyle \#\{\overrightarrow{Q{ }} \in \mathcal{Q}_{k'}(h) \mid P_{\overrightarrow{l^{\ast}}}(k)+rQ(k) \in \mathbf{A}, {}^{\forall}k \in [k_1]\}=\delta^{k_1}\#\mathcal{Q}_{k'}(h)+O_K(\kappa H)$

が高々 $O_K(\kappa H)$ 個の例外を除く $h \in [H]$ に対して成立する。

証明. $k_1$ に関する帰納法で証明する。 $O_K$ -項の定数は $k_1$ 毎に変わるが、 $k_1$ は高々 $K$ 回しか増えないので問題ない。 $k_1=0$ のときは $\overrightarrow{l^{\ast}} \in [L']^{\Omega}$ を任意にとっても成立する( $[0]=\emptyset$ に注意)。よって、 $1 \leq k_1 \leq k_0$ として、 $k_1-1$ では示されたと仮定する。 $N(\varepsilon, \delta, \kappa), N'(\varepsilon, \delta, \kappa, N) \in \mathbb{N}$ はそれぞれ $k_1-1$ に対するそれら以上のもので、記事６の混合補題(iii)の $N_1, N_2$ に対して $N(\varepsilon, \delta, \kappa) \geq N_1(\kappa)$ , $N'(\varepsilon, \delta, \kappa, N) \geq N_2(\kappa, N)$ が成り立つように選択する。このとき、 $\overrightarrow{l^{\ast\ast}} \in [L']^{\Omega}$ が存在して、任意の $k' \in [K] \setminus [k_1-1]$ に対して

$\displaystyle \#\{\overrightarrow{Q{ }} \in \mathcal{Q}_{k'}(h) \mid P_{\overrightarrow{l^{\ast\ast}}}(k)+rQ(k) \in \mathbf{A}, {}^{\forall}k \in [k_1-1]\}=\delta^{k_1-1}\#\mathcal{Q}_{k'}(h)+O_K(\kappa H)$

が高々 $O_K(\kappa H)$ 個の例外を除く $h \in [H]$ に対して成立する。 $h \in [H], k' \in [K]\setminus [k_1]$ に対して $\mathbf{E}_{k', h} \subset [H]$ を

$\mathbf{E}_{k', h}:=\{Q(k_1) \mid \overrightarrow{Q{ }} \in \mathcal{Q}_{k'}(h), \ P_{\overrightarrow{l^{\ast\ast}}}(k)+rQ(k) \in \mathbf{A}, \ {}^{\forall}k \in [k_1-1]\}$

と定義すると、高々 $O_K(\kappa H)$ 個の例外を除く $h \in [H]$ に対して

$\#\mathbf{E}_{k', h}=\delta^{k_1-1}\#\mathcal{Q}_{k'}(h)+O_K(\kappa H)$ −①

が成り立つ( $k'$ と $k_1$ での値が決まれば $\overrightarrow{Q{ }}$ は決まる)。 $l' \in [L']$ に対し、 $\overrightarrow{l^{\ast, l'}} \in [L']^{\Omega}$ を $\overrightarrow{l^{\ast\ast}}$ の $k_1$ -成分を $l'$ に変更したものと定義する。このとき、(iii)より $(P_{\overrightarrow{l^{\ast, l'}}}(k_1) )_{l' \in [L']}$ は $L'$ -APである。よって、

$\displaystyle (P_{\overrightarrow{l^{\ast, l'}}}(k_1)+rh)_{(l', h) \in [L']\times [H]}$

は $L'\times H$ -長方形である。(i)より $H$ -AP $(P_{\overrightarrow{l^{\ast, l'}}}(k_1)+rh)_{h \in [H]} \in \mathcal{P}$ なので、高次多重混合により或る $l' \in [L']$ が存在して

$\displaystyle \#\{h' \in \mathbf{E}_{k', h} \mid P_{\overrightarrow{l^{\ast, l'}}}(k_1)+rh' \in \mathbf{A}\} = \delta \#\mathbf{E}_{k', h}+O_K(\kappa H)$

が高々 $\kappa\#\{([K] \setminus [k_1]) \times [H]\}=O_K(\kappa H)$ 個の例外を除く $(k', h) \in ([K] \setminus [k_1]) \times [H]$ について成立する。 $\overrightarrow{l^{\ast \ast}}$ と $\overrightarrow{l^{\ast, l'}}$ は $k_1-1$ 成分まで一致しているので、 $\mathbf{E}_{k', h}$ の定義と(ii)より左辺は

$\displaystyle \#\{\overrightarrow{Q{ }} \in \mathcal{Q}_{k'}(h) \mid P_{\overrightarrow{l^{\ast, l'}}}(k)+rQ(k) \in \mathbf{A}, \ {}^{\forall}k \in [k_1]\}$

に等しい。従って、①より、任意の $k' \in [K] \setminus [k_1]$ について

$\displaystyle \#\{\overrightarrow{Q{ }} \in \mathcal{Q}_{k'}(h) \mid P_{\overrightarrow{l^{\ast, l'}}}(k)+rQ(k) \in \mathbf{A}, \ {}^{\forall}k \in [k_1]\} = \delta^{k_1}\#\mathcal{Q}_{k'}(h)+O_K(\kappa H)$