インテジャーズ

INTEGERS

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

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

等間隔に並ぶ素数を追い求めて

定理 (帰納的ステップ) 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)

が高々O_K(\kappa H)個を除くh \in [H]について成立する。すなわち、\overrightarrow{l^{\ast}}:=\overrightarrow{l^{\ast, l'}}とすればよい。 Q.E.D.

*1:[0]=\emptysetに注意。