インテジャーズ

INTEGERS

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

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

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

この記事でSzemerédiの定理の組合せ論的証明を完成させる。

帰納的ステップの証明

K \geq 3とし、\Omega \subset [K]は或る0 \leq k_0 < Kに対して[k_0]を含むがk_0+1を含まないと仮定する。C'(K, \Omega)が成り立つと仮定する。以下、\Omega' := (\Omega \setminus [k_0]) \cup \{k_0+1\}とし、C(K, \Omega')が成り立つことを示す。

パラメータの選択

L \in \mathbb{N}を任意にとって、r(K, \Omega', L)をr(K, \Omega', L) \leq \frac{1}{4C_{K, L}'L}を満たすようにとる。ここで、C_{K, L}'は後述のもの。

\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}をその有限色による塗り分け写像とする。\sigma:=\overline{d}_{\mathcal{AP}}(\mathbf{S})とする。このとき、\sigma \geq 1-\varepsilonである。記事５の系より非有界な二重カウンティング性質を満たす\mathcal{P} \subset \mathcal{AP}およびパーフェクトカラーp \in \mathbf{C}が存在して、\mathbf{S}および\mathbf{A} := \{s \in \mathbf{S} \mid c(s)=p\}は\mathcal{P}に沿った密度をもち、d_{\mathcal{P}}(\mathbf{S})=\sigma, d_{\mathcal{P}}(\mathbf{A})=:\delta > 0が成り立つ。

\kappa, \varepsilon' > 0およびL', H, N' \in \mathbb{N}を　

H \geq N_1(\varepsilon'), N' \geq N_2(\varepsilon', H) (N_1, N_2は記事４の命題のもの)。
\varepsilon' < r(K, \Omega, L'), N' \geq N'(L', (\#\mathbf{C}+1)^H) ) (記事９の主張２のもの)。
L' \geq \max\{N(\varepsilon, \delta, \kappa), L\}, H \geq N'(\varepsilon, \delta, \kappa, L') (記事１０のカウンティング補題のもの)。
H \geq N(\varepsilon) (記事４の③のもの)。
\kappa \leq \varepsilon \delta^{k_0}.
H \geq 24K, \frac{\delta^{k_0}}{24KC_K} \geq \kappa (C_Kはカウンティング補題の帰結式に現れるO_Kの定数)。
\kappa < \frac{C_{K, L}'}{2C_K'} (定数の定義は後述)。

を満たすようにとる(証明で使用する順に条件を書いている)。

C'(K, \Omega)およびカウンティング補題の適用

\mathcal{P}が非有界なので、N-AP \overrightarrow{U{ }}=a+r\cdot \overrightarrow{[N]} \in \mathcal{P}が存在する({}^{\exists}a, \in \mathbb{Z}, r, N \in \mathbb{N} (N \geq N'))。記事４の命題の(i)より、高々\varepsilon' N個の例外を除くn \in [N]に対して

(U(n+h) )_{h \in [H]} = U(n)+r\cdot \overrightarrow{[H]} \in \mathcal{P}

が成り立つ。これより、\mathbf{S}' \subset [N]を

\mathbf{S}' := \{n \in [N] \mid U(n)+r\cdot \overrightarrow{[H]}\in \mathcal{P}\}

と定義すれば、\#\mathbf{S}' \geq (1-\varepsilon')Nが成り立つ。色塗り写像 c'\colon \mathbf{S}' \to \mathbf{C}'^{[H]}を

c'(n) := (c(U(n)+rh) )_{h \in [H]}

で定義する。ただし、\mathbf{C}':=\mathbf{C} \sqcup \{\bullet\}とし、写像cをc\colon \mathbb{Z} \to \mathbf{C}'にc(a):= \bullet \ (a \in \mathbb{Z} \setminus \mathbf{S})と拡張しておく。すると、C'(K, \Omega)よりK-APの族 (\overrightarrow{P'_{\overrightarrow{l'}}})_{\overrightarrow{l'} \in [L']^{\Omega}}が存在して次が成り立つ( (ii)は使わない)。

C'(K, \Omega)-(i): 任意の\overrightarrow{l'} \in [L']^{\Omega}に対して、\overrightarrow{P'_{\overrightarrow{l'}}}は\mathbf{S}'に含まれる。
C'(K, \Omega)-(iii): 任意のk \in [K]に対して、(c(U(P'_{\overrightarrow{l'}}(k) )+rh) )_{h \in [H]}は\overrightarrow{l'}=(l'_{k'})_{k' \in \Omega}のk' \leq kに対する成分l_{k'}'にしか依存しない。
C'(K, \Omega)-(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)が成り立つ。

各\overrightarrow{l'} \in [L']^{\Omega}に対して、K-AP \overrightarrow{P_{\overrightarrow{l'}}}を

\displaystyle \overrightarrow{P_{\overrightarrow{l'}}} := \left(U(P'_{\overrightarrow{l'}}(k) )\right)_{k \in [K]}

で定義する。このとき、K-AP族(\overrightarrow{P_{\overrightarrow{l'}}})_{\overrightarrow{l'} \in [L']^{\Omega}}は記事１０のカウンティング補題の条件(i)〜(iii)を満たしている。理由: 条件(i)はC'(K, \Omega)-(i)と\mathbf{S}'の定義から、条件(ii)はC'(K, \Omega)-(iii)と「P_{\overrightarrow{l'}}(k)+rh \in \mathbf{A} \ \Longleftrightarrow \  c(P_{\overrightarrow{l'}}(k)+rh)=p」であることから、条件(iii)はC'(K, \Omega)-(iv)より\overrightarrow{Q_{k, \overrightarrow{l''}}}:=(U(Q'_{k, \overrightarrow{l''}}(l') ) )_{l' \in [L']}とすればわかる。

従って、カウンティング補題(k_1=k_0の場合)より\overrightarrow{l^{\ast}} = (l^{\ast}_k)_{k \in \Omega} \in [L']^{\Omega}が存在して、任意のk' \in [K]\setminus [k_0]に対して

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

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

goodなK-AP族の存在

\mathbf{L} \subset [L']^{\Omega}を

\displaystyle \mathbf{L}:= \{\overrightarrow{l'} = (l'_k)_{k \in \Omega} \in [L']^{\Omega} \mid l'_k = l^{\ast}_k \ ({}^{\forall}k \in [k_0]), \ l'_k \in [L] \ ({}^{\forall}k \in \Omega\setminus [k_0])\}

と定義する(\#\mathbf{L} \leq L^K)。

\mathcal{Q}' := \{\overrightarrow{Q{ }} \in \mathcal{Q} \mid P_{\overrightarrow{l^{\ast}}}(k) + rQ(k) \in \mathbf{A}, \ ({}^{\forall}k \in [k_0])\}

とする。\overrightarrow{Q{ }} \in \mathcal{Q}'がgoodであるとは

P_{\overrightarrow{l'}}(k')+rQ(k') \in \mathbf{S}, \ ({}^{\forall}k' \in [K]\setminus [k_0], \ {}^{\forall}\overrightarrow{l'} \in \mathbf{L})

であることとし、そうでない場合はbadであるということにする。このとき、badな\overrightarrow{Q{ }} \in \mathcal{Q}'の個数は高々

\displaystyle \sum_{\overrightarrow{l'} \in \mathbf{L}}\sum_{k' \in [K]\setminus [k_0]}\sum_{\substack{h \in [H] \\ P_{\overrightarrow{l'}}(k')+rh \not \in \mathbf{S}}}\#(\mathcal{Q}'\cap \mathcal{Q}_{k'}(h) ) −②

である。C'(K, \Omega)-(i)よりP_{\overrightarrow{l'}}(k')+r\cdot \overrightarrow{[H]} \in \mathcal{P}なので、記事４の③より

\#\{h \in [H] \mid P_{\overrightarrow{l'}}(k')+rh \in \mathbf{S}\} \geq (1-2\varepsilon)H

であるので、②の一番内側の和の項数はO(\varepsilon H)である。\#\mathcal{Q}_{k'}(h) \leq Hなので*1、①より高々O_K(\kappa H)個の例外を除くh \in [H]に対して

\#(\mathcal{Q}' \cap \mathcal{Q}_{k'}(h) ) = O_K(\delta^{k_0}H)

が得られる。よって、

\displaystyle \sum_{\substack{h \in [H] \\ P_{\overrightarrow{l'}}(k')+rh \not \in \mathbf{S}}}\#(\mathcal{Q}'\cap \mathcal{Q}_{k'}(h) ) \leq O_K(\kappa H)H+O(\varepsilon H)O_K(\delta^{k_0}H) = O_K(\varepsilon \delta^{k_0}H^2)

なので、②よりbadな\overrightarrow{Q{ }} \in \mathcal{Q}'の個数は高々

\displaystyle \#\mathbf{L} \cdot KO_K(\varepsilon\delta^{k_0}H^2) = O_{K, L}(\varepsilon\delta^{k_0}H^2)

個であることがわかった(定数をC_{K, L}とする)。

[H]^{\circ} := \{h \in [H] \mid \frac{1}{3}H \leq h \leq \frac{2}{3}H\}とする。任意のh \in [H]^{\circ}に対して、\#\mathcal{Q}_{k_0+1}(h) \geq \left\lfloor \frac{H}{3K}\right\rfloorが成り立つ。理由: 1 \leq r \leq \left\lfloor \frac{H}{3K}\right\rfloorに対してK-AP (h+r(k-k_0-1) )_{k \in [K]}は\mathcal{Q}_{k_0+1}(h)の元である。 このとき、①より高々O_K(\kappa H)個(定数をC_K'とする)の例外を除くh \in [H]^{\circ}に対して

\displaystyle \#(\mathcal{Q}'\cap \mathcal{Q}_{k_0+1}(h) ) \geq \delta^{k_0}\frac{H}{4K}

が成り立つ。よって、h \in [H]^{\circ}であって、\mathcal{Q}' \cap \mathcal{Q}_{k_0+1}(h)の全ての元がbadであるようなものは高々O_{K, L}(\varepsilon H)個である。理由: C'_{K, L}\varepsilon H個より多かったと仮定する。ただし、\frac{C_{K, L}'}{8K} > C_{K, L}であるようにとっておく。このとき、badな\overrightarrow{Q{ }} \in \mathcal{Q}'の個数は少なくとも

\displaystyle \delta^{k_0}\frac{H}{4K}(C_{K, L}'\varepsilon H-C_K'\kappa H) > \frac{C_{K, L}'}{8K}\varepsilon \delta^{k_0}H^2 > C_{K, L}\varepsilon \delta^{k_0}H^2

となって矛盾する。よって、高々C'_{K, L}\varepsilon H=O_{K, L}(\varepsilon H)個しかない。

以上により、[H]^{\circ}は区間h_0+[L]であって、任意のh_0+l \in h_0+[L]の元に対して、goodなK-AP \overrightarrow{Q_l} \in \mathcal{Q}' \cap \mathcal{Q}_{k_0+1}(h_0+l)が存在するようなものを含む(これらを固定する)。理由: [H]^{\circ}をLずつ区切った際に、どの区間も\mathcal{Q}' \cap \mathcal{Q}_{k_0+1}(h)の全ての元がbadなhを含んだと仮定する。すると、h \in [H]^{\circ}であって、\mathcal{Q}' \cap \mathcal{Q}_{k_0+1}(h)の全ての元がbadであるようなものが少なくとも

\displaystyle \left\lfloor\frac{\#[H]^{\circ}}{L}\right\rfloor > \frac{H}{4L} > C'_{K, L}\varepsilon H

個は存在することとなり矛盾する。

K-AP族(\overrightarrow{\underline{P}_{\overrightarrow{l{ }}}})_{\overrightarrow{l{ }} \in [L]^{\Omega'}}の構成

そうして、\overrightarrow{l{ }}=(l_k)_{k \in \Omega'} \in [L]^{\Omega'}に対してK-AP \overrightarrow{\underline{P}_{\overrightarrow{l{ }}}}を

\displaystyle \overrightarrow{\underline{P}_{\overrightarrow{l{ }}}}:= \left(P_{\overrightarrow{\underline{l}{ }}}(k)+rQ_{l_{k_0+1}}(k)\right)_{k \in [K]}

と定義し、(\overrightarrow{\underline{P}_{\overrightarrow{l{ }}}})_{\overrightarrow{l{ }} \in [L]^{\Omega'}}に対してC(K, \Omega')の(i)〜(iv)が成立していることを証明する(\overrightarrow{\underline{l}{ }} \in [L']^{\Omega}は\Omega \setminus [k_0]上では\overrightarrow{l{ }}の成分と同じで、[k_0]では\overrightarrow{l^{\ast}}の成分と同じものとする(\overrightarrow{\underline{l}{ }} \in \mathbf{L}) )。

C(K, \Omega')-(i), (ii)の証明

\overrightarrow{l{ }} \in [L]^{\Omega'}を任意にとる。Q_{l_{k_0+1}} \in \mathcal{Q}'なのでk \in [k_0]に対して

P_{\overrightarrow{l^{\ast}}}(k)+rQ_{l_{k_0+1}}(k) \in \mathbf{A} \subset \mathbf{S} −③

が成り立つ。\overrightarrow{\underline{l}{ }}と\overrightarrow{l^{\ast}}は最初の[k_0]の成分は一致しているので、カウンティング補題の条件(ii)より、③から

\underline{P}_{\overrightarrow{l{ }}}(k) = P_{\overrightarrow{\underline{l}{ }}}(k) + rQ_{l_{k_0+1}}(k) \in \mathbf{A} \subset \mathbf{S}, \ ({}^{\forall}k \in [k_0])

が従う。これはC(K, \Omega')-(ii)の成立を意味する。また、k' \in [K]\setminus [k_0]に関してはQ_{l_{k_0+1}}がgoodであることと\overrightarrow{\underline{l}{ }} \in \mathbf{L}であることから

\underline{P}_{\overrightarrow{l{ }}}(k') = P_{\overrightarrow{\underline{l}{ }}}(k') + rQ_{l_{k_0+1}}(k') \in \mathbf{S}

が成り立つ。これで、C(K, \Omega')-(i)が示された。

C(K, \Omega')-(iii)の証明

k \in [K]をとる。\overrightarrow{l{ }}=(l_{k'})_{k' \in \Omega'}, \ \overrightarrow{l'}=(l'_{k'})_{k' \in \Omega'} \in [L]^{\Omega'}はk' \in \Omega' \cap [k]についてl_{k'}=l'_{k'}であると仮定する。このとき、示したいことは

c(\underline{P}_{\overrightarrow{l{ }}}(k) ) = c(\underline{P}_{\overrightarrow{l'}}(k) ) −④

である。k \in [k_0]のときはC(K, \Omega')-(ii)から従うので、k \in [K]\setminus [k_0]とする。するとl_{k_0+1}=l_{k_0+1}'なので

Q_{l_{k_0+1}}(k) = Q_{l'_{k_0+1}}(k) −⑤

が成り立つ。また、\overrightarrow{l{ }}, \overrightarrow{l'} \in \mathbf{L}は\Omega' \cap [k]の成分は一致しているので、C'(K, \Omega)-(iii)より

\displaystyle \left(c(P_{\overrightarrow{\underline{l}{ }}}(k)+rh)\right)_{h \in [H]} = \left(c(P_{\overrightarrow{\underline{l'}}}(k)+rh)\right)_{h \in [H]}

が成り立つ。これと⑤を合わせると、④の成立がわかる。

C(K, \Omega')-(iv)の証明

k \in \Omega'および\overrightarrow{l'} \in [L]^{\Omega'\setminus\{k\}}をとる。\overrightarrow{l{ }}=(l_{k'})_{k' \in \Omega'}は\Omega'\setminus \{k\}上で\overrightarrow{l'}の成分と一致するようなものとする。

k > k_0+1のとき: k \in \Omegaに注意。\overrightarrow{\underline{l'}} \in [L']^{\Omega \setminus \{k\}}を\Omega \setminus ([k_0] \cap \{k\})上では\overrightarrow{l'}の成分で[k_0]上では\overrightarrow{l^{\ast}}の成分であるようなものと定める。すると、\overrightarrow{\underline{l}{ }}は\Omega\setminus \{k\}上で\overrightarrow{\underline{l'}}の成分と一致する。よって

\displaystyle \overrightarrow{Q_{k, \overrightarrow{\underline{l'}}}} := \left(U(Q'_{k, \overrightarrow{\underline{l'}}}(l') )\right)_{l' \in [L']}

とL'-APを定義すると、既に述べたようにK-AP族(\overrightarrow{P_{\overrightarrow{l'}}})_{\overrightarrow{l'} \in [L']^{\Omega}}がカウンティング補題の条件を満たしていることから、その条件(iii)より

\displaystyle Q_{k, \overrightarrow{\underline{l'}}}(l_k) = P_{\overrightarrow{\underline{l}{ }}}(k)

が成り立つ。L-AP \overrightarrow{\underline{Q}_{k, \overrightarrow{l'}}}を

\displaystyle \overrightarrow{\underline{Q}_{k, \overrightarrow{l'}}}:= \left(Q_{k, \overrightarrow{\underline{l'}}}(l)+rQ_{l_{k_0+1}}(k)\right)_{l \in [L]}

と定めると、

\displaystyle \underline{Q}_{k, \overrightarrow{l'}}(l_k) = Q_{k, \overrightarrow{\underline{l'}}}(l_k)+rQ_{l_{k_0+1}}(k) = P_{\overrightarrow{\underline{l}{ }}}(k)+rQ_{l_{k_0+1}}(k) = \underline{P}_{\overrightarrow{l{ }}}(k)

と所望の関係式が得られる。

k=k_0+1のとき: \Omega' \setminus \{k_0+1\} = \Omega \setminus [k_0]なので、l_{k_0+1} \in [L]を動かしても\overrightarrow{\underline{l}{ }}は一意的で動かないことがわかる。そうして、

\displaystyle \underline{P}_{\overrightarrow{l{ }}} = P_{\overrightarrow{\underline{l}{ }}}(k_0+1)+rQ_{l_{k_0+1}}(k_0+1) = P_{\overrightarrow{\underline{l}{ }}}(k_0+1)+r(h_0+l_{k_0+1})

はl_{k_0+1} \in [L]を動かすとL-APをなすことがわかる。

以上で帰納的ステップの証明が完了し、従ってSzemerédiの定理の証明が完全に完了する。 Q.E.D.

*1:\overrightarrow{Q {}}はQ(k_0+1) \in [H]で決まる。