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

一般のSzemerédiの定理を証明する。 $K \geq 3, \Omega \in [K]$ として、次の主張を考える。

主張１ ( $C(K, \Omega)$ ). 任意の $L \in \mathbb{N}$ に対して或る $r(K, \Omega, L) \in \mathbb{R}_{> 0}$ が存在して次が成り立つ: $\varepsilon < r(K, \Omega, L)$ なる $\varepsilon > 0$ をとる。 $\mathbf{S} \subset \mathbb{Z}$ を $\overline{bd}(\mathbf{S}) \geq 1-\varepsilon$ を満たす集合とし、その塗り分け写像 $c\colon \mathbf{S} \to \mathbf{C}$ を考える( $\mathbf{C}$ は有限集合)。このとき、或る $p \in \mathbf{C}$ および $K$ -APの族 $(\overrightarrow{P_{\overrightarrow{l{ }}}})_{\overrightarrow{l{ }} \in [L]^{\Omega}}$ ( $\overrightarrow{l{ }}=(l_k)_{k \in \Omega}$ )が存在して以下の(i)〜(iv)が成立する:
(i) 任意の $\overrightarrow{l{ }} \in [L]^{\Omega}$ に対して、 $\overrightarrow{P_{\overrightarrow{l{ }}}}$ は $\mathbf{S}$ に含まれる。
(ii) $\Omega \neq \emptyset$ かつ $k_0$ を $\Omega$ の最小元とする。このとき、任意の $\overrightarrow{l{ }} \in [L]^{\Omega}$ と $1 \leq k < k_0$ に対して $c(P_{\overrightarrow{l{ }}}(k) )= p$ .
(iii) $k \in [K]$ に対して、任意の $k' \in \Omega \cap [k]$ で $l_{k'}=l'_{k'}$ が成り立つような $\overrightarrow{l{ }}, \overrightarrow{l'} \in [L]^{\Omega}$ は $c(P_{\overrightarrow{l{ }}}(k) ) = c(P_{\overrightarrow{l'}}(k) )$ を満たす。
(iv) $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)$ が成り立つ。

$C(K, \emptyset)$ は成立する: (ii)〜(iv)は主張がない(自動的に成立)。 $[L]^{\emptyset}$ は一点集合なので、(i)については $\mathbf{S}$ の含む $K$ -APの存在を一ついう必要があるが、それは記事４の注意の議論により任意の $L \in \mathbb{N}$ に対して保証できる。

主張１の有限版を考える：

主張２ ( $C'(K, \Omega)$ ). 任意の $L \in \mathbb{N}$ に対して或る $r(K, \Omega, L) \in \mathbb{R}_{> 0}$ が存在して次が成り立つ: $\varepsilon < r(K, \Omega, L)$ なる $\varepsilon > 0$ をとる。また、 $M \in \mathbb{N}$ をとる。このとき、 $N'(L, M)$ が存在して、 $N \geq N'(L, M)$ なる $N \in \mathbb{N}$ に対して次が成立する:
$\mathbf{S} \subset [N]$ を $\#\mathbf{S} \geq (1-\varepsilon)N$ を満たす集合とし、その塗り分け写像 $c\colon \mathbf{S} \to [M]$ を考える。このとき、或る $p \in [M]$ および $K$ -APの族 $(\overrightarrow{P_{\overrightarrow{l{ }}}})_{\overrightarrow{l{ }} \in [L]^{\Omega}}$ ( $\overrightarrow{l{ }}=(l_k)_{k \in \Omega}$ )が存在して $C(K, \Omega)$ の(i)〜(iv)が成立する。

補題 $K \geq 3, \Omega \subset [K]$ に対して $C(K, \Omega)$ が成立すれば $C'(K, \Omega)$ も成立する。

証明. $C(K, \Omega)$ が成立すると仮定して、同じ $r(K, \Omega, N)$ に対して $C'(K, \Omega)$ が成立することを背理法で証明する。すなわち、 $L \in \mathbb{N}$ と $\varepsilon < r(K, \Omega, L)$ をとって、各 $i \in \mathbb{N}$ に対して $N_i \to \infty \ (i \to \infty)$ となるような $N_i \in \mathbb{N}$ , $\#\mathbf{S}_i \geq (1-\varepsilon)N_i$ を満たす集合 $\mathbf{S}_i \subset [N_i]$ 、 $M$ 色塗り分け写像 $c_i\colon \mathbf{S}_i \to [M]$ が存在して、どの $i$ に対しても $N \mapsto N_i, \mathbf{S} \mapsto \mathbf{S}_i$ とした際に $C'(K, \Omega)$ の主張が成り立たないようなものが存在したと仮定する。

$[N_i]$ を適切に $h_i+[N_i]$ に平行移動する: どの二つの $h_i+[N_i]$ もdisjointであるようにどんどん右の方に平行移動し、任意の $i \in \mathbb{N}$ に対して「任意の $K$ -APおよび $L$ -APについて、それを構成する少なくとも二つの元が $\bigsqcup_{i' < i}(h_{i'}+[N_{i'}])$ に含まれている場合は $h_i+[N_i]$ には含まれない」が満たされるようにする。このとき、 $\bigsqcup_{i \in \mathbb{N}}(h_i+[N_i])$ に含まれる $K$ -APおよび $L$ -APは必ず一つの $h_i+[N_i]$ に含まれなければならない。

そうして、 $\displaystyle \mathbf{S} := \bigsqcup_{i \in \mathbb{N}}(h_i+\mathbf{S}_i)$ とする。このとき、 $\overline{bd}(\mathbf{S}) \geq 1-\varepsilon$ であり、 $\mathbf{S}$ に含まれる $K$ -APおよび $L$ -APは必ず一つの $h_i+\mathbf{S}_i$ に含まれなければならないことがわかる。

$\mathbf{S}$ の $M$ 色塗り分け写像 $c\colon \mathbf{S} \to [M]$ を $h_i+n_i \in h_i+\mathbf{S}_i$ に対して $c(h_i+n_i) := c_i(n_i)$ で定義する。すると、定理１より或る色 $p \in [M]$ および $K$ -APの族 $(\overrightarrow{P_{\overrightarrow{l{ }}}})_{\overrightarrow{l{ }} \in [L]^{\Omega}}$ が存在して $\mathbf{S}$ について $C(K, \Omega)$ の(i)〜(iv)が成立する。

(i)と $\mathbf{S}$ の構成より或る $i$ が存在して $\overrightarrow{P_{\overrightarrow{l{ }}}}$ は $h_i+\mathbf{S}_i$ に含まれ、(iv)より $\overrightarrow{l{ }}$ の一つの成分 $l_k$ を動かすとき(他の成分は固定) $i$ は変化しない( $\overrightarrow{Q_{k, \overrightarrow{l'}}} \subset h_i+\mathbf{S}_i$ よりわかる)。よって、 $i$ は $\overrightarrow{l{ }} \in [L]^{\Omega}$ に依存しない。すると、 $\overrightarrow{P_{\overrightarrow{l{ }}}}$ を $-h_i$ だけ平行移動することによって $\mathbf{S}_i$ が主張を満たすことになり、背理法の仮定に矛盾する。 Q.E.D.

命題 $K \geq 3$ に対して $C'(K, \{K\})$ が成立すると仮定する。このとき、 $\mathbf{A} \subset \mathbb{N}$ が $\overline{bd}(\mathbf{A}) > 0$ を満たすならば $\mathbf{A}$ は或る $(K-1)$ -APを含む。

証明. $\delta:=\overline{d}_{\mathcal{AP}}(\mathbf{A}) \geq \overline{bd}(\mathbf{A}) > 0$ とする( $0 < \delta \leq 1$ )。密度昇格定理より非有界かつ二重カウンティング性質を満たすような $\mathcal{P} \subset \mathcal{AP}$ が存在し、 $\mathbf{A}$ の $\mathcal{P}$ に沿った密度が存在して $d_{\mathcal{P}}(\mathbf{A}) = \delta$ が成り立つ。 $\varepsilon < r(K, \{K\}, 1)$ をとる。また、記事４の命題における $N_1(\varepsilon)$ および $N_2(\varepsilon, N)$ に対して $\max\{N_1(\varepsilon), N(\delta/2)\} \leq H \leq N_2(\varepsilon, H) \leq N'$ なる $H, N' \in \mathbb{N}$ をとる( $N(\delta/2)$ は記事４の③に対する整数)。 $\mathcal{P}$ は非有界なので、 $N \geq N'$ を満たす $N \in \mathbb{N}$ に対して $\overrightarrow{P{ }} \in \mathcal{P}$ なる $N$ -APが存在する。記事４の命題の(i)より $\varepsilon N$ 個の例外を除く $n \in [N ]$ に対して $H$ -AP $(P(n+h) )_{h \in [H]} \in \mathcal{P}$ が成り立つ。よって、

$\mathbf{S} := \{n \in [N] \mid P(n+h)_{h \in [H]} \in \mathcal{P}\}$

と $\mathbf{S}$ を定義すると $\#\mathbf{S} \geq (1-\varepsilon)N$ が成り立つ。 $\mathbf{S}$ の $2^H$ 色塗り分けを $n \in \mathbf{S}$ の色を

$\{h \in [H] \mid P(n+h) \in \mathbf{A}\} \subset [H]$

と定めることによって定義する。このとき、 $C'(K, \{K\})$ より $K$ -AP $\overrightarrow{Q{ }}\subset \mathbf{S}$ が存在して $Q(1), \dots, Q(K-1)$ は同じ色である。すなわち、

$\{h \in [H] \mid P(Q(1)+h) \in \mathbf{A}\} = \cdots = \{h \in [H] \mid P(Q(K-1)+h) \in \mathbf{A}\}=p$

が成り立つ。 $H$ -AP $(P(Q(k)+h) )_{h \in [H]}$ は任意の $k \in [K]$ に対して $\mathcal{P}$ に属し、 $d_{\mathcal{P}}(\mathbf{A}) = \delta > 0$ なので、記事４の③より $p \neq \emptyset$ がわかる。すなわち、或る $h \in [H]$ が存在して、任意の $k \in [K-1]$ に対して $P(Q(k)+h) \in \mathbf{A}$ が成り立ち、 $\mathbf{A}$ は $(K-1)$ -AP $(P(Q(k)+h) )_{k \in [K-1]}$ を含む。 Q.E.D.

INTEGERS

数、特に整数に関する記事。

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