2017-12-14

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

以上の道具立てに基づくRothの定理(Szemerédiの定理の $K=3$ の場合)の証明を実行する。Szemerédiの定理の証明に論理的には必要のない部分であるが、プロトタイプとして一度練習できる*1。また、後のSzemerédiの定理の証明と比較して、特殊な議論によるショートカットが存在する。

定理１ ( $C(3, \{2\})$ ). $L \in \mathbb{N}$ とし、 $\mathbf{S} \subset \mathbb{Z}$ は $\overline{bd}(\mathbf{S}) \geq 1-\frac{1}{10L}$ を満たし、有限個の色で塗り分けられているとする。このとき、或る色の類 $\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) \in \mathbf{A}$ .
(iii) $(P_l(2) )_{l \in [L]}$ は $L$ -APをなす。

証明. $\overline{bd}(\mathbf{S}) \geq 1-\frac{1}{10L}$ より、 $N \geq 72L$ を満たす十分大きい $N \in \mathbb{N}$ と或る $h \in \mathbb{Z}$ が存在して

$\displaystyle \#\{\mathbf{S} \cap (h+[N])\} \geq \left(1-\frac{1}{9L}\right)N$

が成り立つ。よって、或る $n_0 \in \left[\left\lfloor \frac{N}{8L}\right\rfloor\right]$ が存在して $h+n_0 \in \mathbf{S}$ が成り立つ(背理法で示せる)。 $h+n_0$ の色の類を $\mathbf{A}$ とする。

$r \in \left[\left\lfloor\frac{N}{3}\right\rfloor\right]$ がgoodであるとは $h+n_0+r, h+n_0+2r \in \mathbf{S}$ であることと定義し、それ以外のときはbadであるとよぶことにする。 $h+n_0+r, h+n_0+2r \in h+[N]$ なので*2、 $\left[\left\lfloor\frac{N}{3}\right\rfloor\right]$ には高々 $\frac{2N}{9L}$ 個しかbadな元が存在しない*3。よって、 $\left[\left\lfloor\frac{N}{3}\right\rfloor\right]$ は全ての元がgoodであるような区間 $n_1+[L]$ を含む。理由: $\left\lfloor\frac{N}{3}\right\rfloor \geq \left(\left\lfloor\frac{N}{3L}\right\rfloor-1\right)L$ なので、もし $\left[\left\lfloor\frac{N}{3}\right\rfloor\right]$ を長さ $L$ ずつに区切ったときに全ての区間がbadな元を含めば

badな元の個数 $\displaystyle \geq \left\lfloor\frac{N}{3L}\right\rfloor-1 > \frac{2N}{9L}$

となって矛盾する。任意の $l \in [L]$ に対して

$\displaystyle \overrightarrow{P_l} := (h+n_0, h+n_0+(n_1+l), h+n_0+2(n_1+l) )$

とする。すると、goodの定義によって $\overrightarrow{P_l}$ は $\mathbf{S}$ に含まれ、 $P_l(1) = h+n_0 \in \mathbf{A}$ であり、

$\displaystyle (P_l(2) )_{l \in [L]} = (h+n_0+n_1+1, \dots, h+n_0+n_1+L)$

は $L$ -APをなしている*4。 Q.E.D.

次に定理１の有限版を示す。

定理２ ( $C'(3, \{2\})$ ). $L, M \in \mathbb{N}$ に対して $N(L, M)$ が存在して、 $N \geq N(L, M)$ なる整数 $N$ に対して次が成立する: $\mathbf{S} \subset [N]$ が $\#\mathbf{S} \geq \left(1-\frac{1}{10L}\right)N$ を満たし、 $M$ 色に塗り分けられているとする。このとき、或る色の類 $\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)〜(iii)を満たす。

証明. 背理法で証明する。すなわち、各 $i \in \mathbb{N}$ に対して $N_i \to \infty \ (i \to \infty)$ となるような $N_i \in \mathbb{N}$ , $\#\mathbf{S}_i \geq \left(1-\frac{1}{10L}\right)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$ とした際に定理の主張が成り立たないようなものが存在したと仮定する。

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

そうして、 $\displaystyle \mathbf{S} := \bigsqcup_{i \in \mathbb{N}}(h_i+\mathbf{S}_i)$ とする。このとき、 $\overline{bd}(\mathbf{S}) \geq 1-\frac{1}{10L}$ であり、 $\mathbf{S}$ に含まれる $3$ -APおよび $L$ -AP ( $L \geq 3$ )は必ず一つの $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)$ で定義する。すると、定理１より或る色の類 $\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]}$ が存在して $\mathbf{S}$ について(i)〜(iii)が成立する。

(i)と $\mathbf{S}$ の構成より或る $i$ が存在して $\overrightarrow{P_l}$ は $h_i+\mathbf{S}_i$ に含まれ、(iii)より $i$ は $l \in [L]$ に依存しないことがわかる。すると、 $\overrightarrow{P_l}$ を $-h_i$ だけ平行移動することによって $\mathbf{S}_i$ が主張を満たすことになり、背理法の仮定に矛盾する。 Q.E.D.

定理３ ( $C(3, \{3\})$ ). $L \in \mathbb{N}$ とし、 $\mathbf{S} \subset \mathbb{Z}$ は $\overline{bd}(\mathbf{S}) \geq 1-\frac{1}{50L}$ を満たし、有限個の色で塗り分けられているとする。このとき、或る色の類 $\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をなす。

証明. $\sigma := \overline{d}_{\mathcal{AP}}(\mathbf{S})$ とする。仮定より $\sigma \geq 1-\frac{1}{50L}$ である。記事５の系より、パーフェクトカラーの類 $\mathbf{A} \subset \mathbf{S}$ および非有界で二重カウンティング性質を満たす $\mathcal{P} \subset \mathcal{AP}$ が存在して、 $\mathbf{A}$ と $\mathbf{S}$ は $\mathcal{P}$ に沿った密度を持ち、 $d_{\mathcal{P}}(\mathbf{A}):=\delta > 0$ かつ $d_{\mathcal{P}}(\mathbf{S})=\sigma$ が成り立つ。

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

$L' \geq N_1(\frac{\delta}{100}), H \geq \max\{N_1(\frac{1}{10L'}), N_2(\frac{\delta}{100}, L')\}, N' \geq N_2(\frac{1}{10L'}, H)$ ( $N_1, N_2$ は記事４の命題もの)。
$L'$ は記事４の③の $\varepsilon=\delta$ に対する $N$ 以上。
$H$ は記事４の③の $\varepsilon=\delta/2$ に対する $N$ 以上。
$H \geq 180 L'$ .
$L' \geq N_1^{(\mathrm{iii})}(\frac{\delta^2}{10L}), H \geq N_1^{(\mathrm{iii})}(\frac{\delta^2}{10L}, L')$ ( $N_1^{(\mathrm{iii})}, N_2^{(\mathrm{iii})}$ は記事６の定理のもの)。
$H$ は記事４の③の $\varepsilon=\frac{1}{90L}$ に対する $N$ 以上。
$H \geq 300L$ .

を満たすように選ぶ。

$\mathcal{P}$ は非有界なので、或る $N$ -AP $\overrightarrow{U{ }} \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}{10L'}\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) \in \mathbf{A}'$ .
(iii) $(P_{l'}(2) )_{l' \in [L']}$ は $L'$ -APをなす。

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

$\{h \in [H] \mid U(P_{l'}(1)+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$ −②

がわかる。①が成り立つので、記事４の命題の(i)より各 $l' \in [L']$ について、高々 $\frac{\delta}{100}H$ 個の例外を除く $h \in [H]$ に対して $L'$ -AP $(U(P_{l'}(1)+h+l) )_{l \in [L']} \in \mathcal{P}$ −③が成り立つ。よって、記事４の③より

$\#\{\mathbf{P} \cap (h+[L'])\} \leq 2 \delta L'$ −④

が高々 $\frac{\delta}{100}H$ 個の例外を除く $h \in [H]$ に対して成り立つ。このことから、

$\displaystyle \#\{h \in \mathbf{P} \mid h \geq \frac{9}{10}H\} \leq \frac{\delta}{4}H$

が従う。理由: ③が成り立つような $h \in [H]$ をgood、成り立たないような $h \in [H]$ をbadとよぶことにする。このとき、

$\displaystyle[\frac{9}{10}H, H] \subset \bigsqcup_{i=1}^k(h_i+[L']) \sqcup X$

なる被覆がある。ここで、 $h_1, \dots, h_k$ はgoodで、 $X \subset [\frac{9}{10}H, H]$ はbadな点から成る集合であり、 $k < \frac{H}{9L'}$ および $\#X \leq \frac{\delta}{100}H$ が成り立つ。このような被覆の存在性は、例えば $[\frac{9}{10}H, H]$ の最小元から考えて $h$ がgoodなら $h+[L']$ を選んで $h+[L']+1$ に移り、badなら $h$ を $X$ の元として $h+1$ に移るというアルゴリズムを考えればよい。このような被覆の存在により、④によって

$\displaystyle \#\{h \in \mathbf{P} \mid h \geq \frac{9}{10}H\} \leq 2\delta L'k+\#X < \frac{2\delta}{9}H+\frac{\delta}{100}H < \frac{\delta}{4}H$

がわかる。よって、②より

$\displaystyle \#\{h \in \mathbf{P} \mid h < \frac{9}{10}H\} \geq \frac{\delta}{4}H$

である。鳩ノ巣原理により、或るパリティ $i \in \mathbb{Z}/2\mathbb{Z}$ が存在して

$\displaystyle \#\{h \in \mathbf{P} \mid h < \frac{9}{10}H, h \bmod{2} = i\} \geq \frac{\delta}{8}H$ −⑤

が成り立つ( $i$ を取って固定する)。 $\mathbf{W}$ を

$\displaystyle \mathbf{W} := \{h \in \mathbb{N} \mid \frac{9}{10}H \leq h \leq H, h \bmod{2} = i \}$

と定義する。 $\frac{1}{30}H \leq \#\mathbf{W} \leq \frac{1}{10}H$ −⑥である。⑤より各 $h \in \mathbf{W}$ に対して、 $Q(1) \in \mathbf{P}, Q(3) = h$ であるような $3$ -AP $\overrightarrow{Q{ }} \subset [H]$ が少なくとも $\frac{\delta}{8}H$ 個存在する。理由: ⑤の左辺の集合の元を任意にとったとき、その元と $h$ の中点を考えれば $3$ -APが得られる(パリティが揃っているので中点は整数)。 $\overrightarrow{Q{ }}$ を動かしたときの $Q(2)$ のなす集合を $\mathbf{E}_h$ とする。

$\displaystyle \#\mathbf{E}_h \geq \frac{\delta}{8}H, \quad h \in \mathbf{W}$ −⑦

である。ここで、 $\overrightarrow{R{ }}:=(U(P_{l'}(2)+h) )_{(l', h) \in [L'] \times [H]}$ とすると、(iii)より $\overrightarrow{R{ }}$ は $L' \times H$ -長方形である。(i)と $\mathbf{S}'$ の定義より、任意の $l' \in [L']$ に対して $\overrightarrow{R^{l'}} \in \mathcal{P}$ . 記事６の混合補題の(iii)(高次多重混合)により、或る $l' \in [L']$ が存在して(以下固定)、高々 $\frac{\delta^2}{10L}\mathbf{W}$ 個の例外を除く $h \in \#\mathbf{W}$ に対して

$\displaystyle \left|\#\{h' \in \mathbf{E}_h \mid U(P_{l'}(2)+h') \in \mathbf{A}\}-\delta \mathbf{E}_h\right| \leq \frac{\delta^2}{10L}H$

が成り立ち、⑦より

$\displaystyle \#\{h' \in \mathbf{E}_h \mid U(P_{l'}(2)+h') \in \mathbf{A}\} \geq \delta \#\mathbf{E}_h-\frac{\delta^2}{10L}H \geq \frac{\delta^2}{8}H-\frac{\delta^2}{10L}H > 0$ −⑧

を得る。⑥より例外個数は高々 $\frac{\delta^2}{10L}\#\mathbf{W} \leq \frac{1}{100L}H$ 個である。また、(i)より $H$ -AP $(U(P_{l'}(3)+h) )_{h \in [H]} \in \mathcal{P}$ であり、 $d_{\mathcal{P}}(\mathbf{S}) \geq 1-\frac{1}{50L}$ なので、記事４の③より

$\displaystyle U(P_{l'}(3)+h) \in \mathbf{S}$ −⑨

が高々 $\frac{1}{50L}H$ 個の例外を除く $h \in [H]$ に対して成立する。 $\mathbf{W}$ を最小元から $L$ 個ずつに分けると、少なくとも一つの部分集合は⑧と⑨をともに満たす元のみからなる。理由: $L$ 個ずつに分けた部分集合達は、⑥より少なくとも $\left\lfloor \frac{\#W}{L}\right\rfloor > \frac{1}{30L}H-1$ 個ある。一方、⑧、⑨のどちらかを満たさないような $\mathbf{W}$ の元は高々 $\frac{1}{100L}H+\frac{1}{50L}H \leq \frac{1}{30L}H-1$ 個しかない。つまり、 $\mathbf{W}$ は或る $L$ -AP $h_0+2\cdot \overrightarrow{[L]}$ であって、どの $h \in h_0+2\cdot [L]$ も⑧、⑨を満たすようなものが存在する( $\mathbf{W}$ の元が同じパリティのもののみから構成されていることに注意)。このとき、⑧と各構成より、各 $h \in h_0+2\cdot [L]$ に対して、 $[H]$ に含まれる $3$ -AP $\overrightarrow{Q_h}$ であって、 $Q_h(1) \in \mathbf{P}$ , $U(P_{l'}(2)+Q_h(2) ) \in \mathbf{A}$ , $Q_h(3) = h$ であるようなものが存在する。そうして、 $L$ 個の $3$ -AP

$( (U(P_{l'}(1)+Q_{h_0+2l}(1) ), (U(P_{l'}(2)+Q_{h_0+2l}(2) ), (U(P_{l'}(3)+Q_{h_0+2l}(3) ) )_{l \in [L]}$

を考える。 $P_{l'}, Q_{h_0+2l}, U$ は全てAPなので、これは確かに $3$ -APの族である。直前の $\overrightarrow{Q_h}$ の性質および⑨、 $Q_{h_0+2l}(3)=h_0+2l$ から主張の(i), (ii), (iii)を満たしていることがわかる。 Q.E.D.

定理４ ( $C'(3, \{3\})$ ). $L, M \in \mathbb{N}$ に対して $N(L, M)$ が存在して、 $N \geq N(L, M)$ なる整数 $N$ に対して次が成立する: $\mathbf{S} \subset [N]$ が $\#\mathbf{S} \geq \left(1-\frac{1}{50L}\right)N$ を満たし、 $M$ 色に塗り分けられているとする。このとき、或る色の類 $\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)〜(iii)を満たす。

証明. 定理３から導出する方法は定理２の証明と全く同様なので省略する。 Q.E.D.

*1:TaoによるSzemerédiの定理の証明の帰納的論法の部分では $K$ を動かすので、例えば $K=3$ に限って証明を書き下すことはできない(意味がない)。一方で、Szemerédiによる証明の帰納的論法の部分では $K$ を動かさない。