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

Rothの定理の証明. $\mathbf{A} \subset \mathbb{N}$ を $\overline{bd}(\mathbf{A}) > 0$ を満たすような集合とする。示したいことは、 $\mathbf{A}$ が $3$ -APを少なくとも一つは含むことである。

$\delta:=\overline{d}_{\mathcal{AP}}(\mathbf{A})$ とすると、 $\delta \geq \overline{bd}(\mathbf{A}) > 0$ である。密度昇格定理によって非有界かつ二重カウンティング性質を満たすような $\mathcal{P} \subset \mathcal{AP}$ が存在し、 $\mathbf{A}$ の $\mathcal{P}$ に沿った密度が存在して $d_{\mathcal{P}}(\mathbf{A}) = \delta$ が成り立つ。

$L \leq H \leq N'$ なる正整数 $L, H, N'$ を

$H \geq N_1(\frac{1}{50L}), N' \geq N_2(\frac{1}{50L}, H)$ ( $N_1, N_2$ は記事４の命題もの)。
$H$ は記事４の③の $\varepsilon=\delta/2$ に対する $N$ 以上。
$\frac{\log_2H+1}{H} \leq \frac{\delta}{4}.$
$L \geq N_1^{(\mathrm{i})}(\delta^2/8), H \geq N_1^{(\mathrm{i})}(\delta^2/8, L)$ ( $N_1^{(\mathrm{i})}, N_2^{(\mathrm{i})}$ は記事６の定理のもの)。

を満たすように選ぶ。

$\mathcal{P}$ は非有界なので、或る $N$ -AP $\overrightarrow{U{ }} = (U(n) )_{n \in [N]} \in \mathcal{P}$ が存在する(一つとって固定。 $N \geq N'$ )。そして、 $\mathbf{S}' \subset [N]$ を

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

と定義する。記事４の命題の(i)より

$\displaystyle \#\mathbf{S}' \geq \left(1-\frac{1}{50L}\right)N$

が成り立つ。色塗り写像 $c\colon \mathbf{S}' \to 2^{[H]}$ を

$c(n) := \{h \in [H] \mid U(n+h) \in \mathbf{A}\}$

と定義する。すると、記事７の定理４より或る色の類 $\mathbf{A}' \subset \mathbf{S}'$ および $3$ -AP $\overrightarrow{P_{l}}=(P_{l}(1), P_{l}(2), P_{l}(3) )$ の族 $(\overrightarrow{P_{l}})_{l \in [L]}$ が存在して、

(i) 任意の $l \in [L]$ に対して $\overrightarrow{P_{l}}$ は $\mathbf{S}'$ に含まれる。
(ii) 任意の $l \in [L]$ に対して $P_{l}(1), P_l(2) \in \mathbf{A}'$ .
(iii) $(P_{l}(3) )_{l \in [L]}$ は $L$ -APをなす。

が成り立つ*1。 $\mathbf{A}'$ の元の色を $\mathbf{P} \subset [H]$ とすると、(ii)より任意の $l \in [L]$ に対して

$\{h \in [H] \mid U(P_{l}(1)+h) \in \mathbf{A}\} = \{h \in [H] \mid U(P_{l}(2)+h) \in \mathbf{A}\} = \mathbf{P}$

が成り立つ。(i)より $H$ -AP $(U(P_{l}(1)+h) )_{h \in [H]} \in \mathcal{P}$ であり $d_{\mathcal{P}}(\mathbf{A})=\delta$ なので、記事４の③より

$\displaystyle \#\mathbf{P} \geq \frac{\delta}{2}H$ −①

がわかる。 $\mathbf{E} \subset [H]$ を $[H]$ に含まれる $3$ -AP $\overrightarrow{Q{ }}=(Q(1), Q(2), Q(3) )$ であって、 $Q(1), Q(2) \in \mathbf{P}$ が成り立つようなものの $Q(3)$ のなす集合と定義する。このとき、

$\displaystyle \#\mathbf{E} \geq \frac{\delta}{4}H$ −②

が成り立つ。理由: $\#\mathbf{E} < \frac{\delta}{4}H$ と仮定する。任意の $h \in \mathbf{P}$ に対して、 $g \in (h, \frac{h+H}{2}]$ 毎に $\overrightarrow{Q{ }}=(h, g, 2g-h)$ を作ることができる( $2g-h \in \mathbf{E}$ )。 $\mathbf{P}$ の最小元を $h_0$ とし、 $h_1, \dots, h_k$ を $\frac{h_i+H}{2}$ より大きい $\mathbf{P}$ の最小元が $h_{i+1}$ であるように順に定める。 $k$ は

$\displaystyle \mathbf{X} := \bigsqcup_{i=0}^k\left\{\left(h_i, \frac{h_i+H}{2}\right] \cap \mathbf{P}\right\}$

として、 $\mathbf{X} \cup \{h_0, \dots, h_k\} = \mathbf{P}$ となる番号とする。すると、 $k \leq \lfloor \log_2H\rfloor$ である。このとき、

$\displaystyle \#\mathbf{P} =\#\mathbf{X}+(k+1) \leq \#\mathbf{E}+(k+1) < \frac{\delta}{4}H+\log_2H+1 \leq \frac{\delta}{2}H$

となって①に矛盾する。

(iii)より、 $\overrightarrow{R{ }} := (U(P_l(3)+h) )_{(l, h) \in [L]\times [H]}$ は $L\times H$ -長方形であり、(i)より任意の $l \in [L]$ に対して $\overrightarrow{R^l} \in \mathcal{P}$ である。記事６の混合補題の(i)(単混合)により、或る $l \in [L]$ が存在して(以下固定)、②より

$\displaystyle \#\{h \in \mathbf{E} \mid U(P_l(3)+h) \in \mathbf{A} \} \geq \delta \#\mathbf{E}-\frac{\delta^2}{8} H > 0$

が成り立つ。よって、 $[H]$ 内の $3$ -AP $\overrightarrow{Q{ }}=(Q(1), Q(2), Q(3) )$ であって、 $Q(1), Q(2) \in \mathbf{P}$ , $U(P_l(3)+Q(3) ) \in \mathbf{A}$ を満たすものが存在する。このとき、 $3$ -AP