インテジャーズ

INTEGERS

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

タオのセメレディ論文の§10を読む(その二)

この記事でSzemerédiの定理の証明が完結します。


§6(その一)の補題3直後の式、Cauchy-Schwarzの不等式、前記事④より、任意の0 \leq m \leq (k-1)N_0に対して

\displaystyle \int_{\mathbb{Z}_N}\left.\mathbb{E}\left(\left|T^{\mu m}f_{UAP}-F_{\mu m}\right| \right| \mathcal{B}''\right) = \int_{\mathbb{Z}_N}\left|T^{\mu m}f_{UAP}-F_{\mu m}\right| \leq \left\|T^{\mu m}f_{UAP}-F_{\mu m}\right\|_{L^2} \ll N_0^{-1}

が成り立つ。従って、Markovの不等式より

\displaystyle \mathbb{P}_{\mathbb{Z}_N}\left(\left.\mathbb{E}\left(\left|T^{\mu m}f_{UAP}-F_{\mu m}\right|\right|\mathcal{B}''\right) \geq \frac{\delta}{16k} \right) \leq \frac{16k}{\delta}\int_{\mathbb{Z}_N}\left.\mathbb{E}\left(\left|T^{\mu m}f_{UAP}-F_{\mu m}\right|\right|\mathcal{B}''\right) \ll N_0^{-1} −①

である。n \in \mathbb{Z}_Nに対してE_n'

\displaystyle E_n':=\left\{x \in \mathbb{Z}_N\left|\left.\mathbb{E}(T^nf_{U^{\perp}}\right|\mathcal{B}'')(x) \geq \frac{\delta}{2}, \ \left. \mathbb{E}(\left|T^nf_{U^{\perp}}-T^nf_{UAP}\right| \right| \mathcal{B}'')(x) \leq \frac{\delta}{16k}\right\}\right.

と定義する。このとき、各1 \leq \lambda \leq N_0/k_{\ast}に対して

\displaystyle \mathbb{P}_{\mathbb{Z}_N}\left( \bigcap_{m=1}^{k_{\ast}}E_{\mu \lambda m}\right) \geq \mathbb{P}_{\mathbb{Z}_N}\left( \bigcap_{m=1}^{k_{\ast}}E_{\mu \lambda m}'\right)-O(N_0^{-1}) −②

が成り立つ。理由: n \in \mathbb{Z}_Nに対してD_n

\displaystyle D_n:=\left\{x \in \mathbb{Z}_N \left| \left.\mathbb{E}\left(\left|T^nf_{UAP}-F_n\right| \right|\mathcal{B}''\right)(x) \geq \frac{\delta}{16k}\right\}\right.

と定める。すると、集合の包含関係

\displaystyle \bigcap_{m=1}^{k_{\ast}}E_{\mu \lambda m}' \setminus \bigcup_{m=1}^{k_{\ast}}D_{\mu \lambda m} \subset \bigcap_{m=1}^{k_{\ast}}E_{\mu \lambda m}

が成り立つ。理由: x \in \bigcap_{m=1}^{k_{\ast}}E_{\mu \lambda m}' \setminus \bigcup_{m=1}^{k_{\ast}}D_{\mu \lambda m}であれば、任意の1 \leq m \leq k_{\ast}に対して

\displaystyle \left.\mathbb{E}\left(\left|T^{\mu \lambda m}f_{U^{\perp}}-T^{\mu \lambda m}f_{UAP}\right|\right|\mathcal{B}''\right)(x) \leq \frac{\delta}{16k}

及び

\displaystyle \left.\mathbb{E}\left(\left|T^{\mu \lambda m}f_{UAP}-F_{\mu \lambda m}\right|\right|\mathcal{B}''\right)(x) < \frac{\delta}{16k}

が成り立つので、三角不等式より

\displaystyle \left.\mathbb{E}\left(\left|T^{\mu \lambda m}f_{U^{\perp}}-F_{\mu \lambda m}\right|\right|\mathcal{B}''\right)(x) < \frac{\delta}{8k}

となって、x \in \bigcap_{m=1}^{k_{\ast}}E_{\mu \lambda m}がわかる 従って、

\displaystyle \#\left(\bigcap_{m=1}^{k_{\ast}}E_{\mu \lambda m} \right) \geq \#\left(\bigcap_{m=1}^{k_{\ast}}E_{\mu \lambda m}'\right) - \sum_{m=1}^{k_{\ast}}\#D_{\mu \lambda m}

と評価できる。1 \leq \lambda m \leq N_0なので*1、①より

\displaystyle \mathbb{P}_{\mathbb{Z}_N}(D_{\mu \lambda m}) \ll N_0^{-1}

であり、k_{\ast}=O(1)であることから所望の不等式を得る

補題1 (\mathcal{B}''のエフェクティブなシフト不変性, Lemma 10.3)
-(k-1)N_0 \leq m \leq (k-1)N_0を満たす或るmが存在して

\displaystyle \left\|\left.\mathbb{E}\left(T^{\mu m}f_{U^{\perp}}\right|\mathcal{B}''\right)-T^{\mu m}\left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}''\right)\right\|_{L^2} \geq N_0^{-1}

または

\displaystyle \left\|\left.\mathbb{E}\left(T^{\mu m}\left|f_{U^{\perp}}-f_{UAP}\right|\right|\mathcal{B}''\right)-T^{\mu m}\left.\mathbb{E}\left(\left|f_{U^{\perp}}-f_{UAP}\right|\right|\mathcal{B}''\right)\right\|_{L^2} \geq N_0^{-1}

が成り立てば、ダイコトミーの(エネルギー増加)が生じる。

証明. §6(その一)の補題6より

\displaystyle \left.\mathbb{E}\left(T^{\mu m}f_{U^{\perp}}\right|\mathcal{B}''\right) = T^{\mu m}\left.\mathbb{E}\left(f_{U^{\perp}}\right|T^{-\mu m}\mathcal{B}''\right)

が成り立つので、

\displaystyle \left\|\left.\mathbb{E}\left(T^{\mu m}f_{U^{\perp}}\right|\mathcal{B}''\right)-T^{\mu m}\left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}''\right)\right\|_{L^2} \geq N_0^{-1}

であれば、\left\| \cdot \right\|_{L^2}のシフト不変性*2から

\displaystyle \left\|\left.\mathbb{E}\left(f_{U^{\perp}}\right|T^{-\mu m}\mathcal{B}''\right)-\left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}''\right)\right\|_{L^2} \geq N_0^{-1}

が成り立つ。もし、この状況で

\displaystyle \left\|\left.\mathbb{E}\left(f_{U^{\perp}}\right|T^{-\mu m}\mathcal{B}''\right)-\left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}'\right)\right\|_{L^2} < \frac{1}{2}N_0^{-1}

かつ

\displaystyle \left\|\left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}''\right)-\left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}'\right)\right\|_{L^2} < \frac{1}{2}N_0^{-1}

であれば、三角不等式によって

\displaystyle \left\|\left.\mathbb{E}\left(f_{U^{\perp}}\right|T^{-\mu m}\mathcal{B}''\right)-\left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}''\right)\right\|_{L^2} < N_0^{-1}

となって矛盾する。従って、

\displaystyle \left\|\left.\mathbb{E}\left(f_{U^{\perp}}\right|T^{-\mu m}\mathcal{B}''\right)-\left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}'\right)\right\|_{L^2} \geq \frac{1}{2}N_0^{-1} −③

または

\displaystyle \left\|\left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}''\right)-\left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}'\right)\right\|_{L^2} \geq \frac{1}{2}N_0^{-1} −④

である。④が成り立つと仮定しよう。§7のエネルギーギャップ公式より

\displaystyle \mathcal{E}_{\boldsymbol{f}}(\mathcal{B}'')-\mathcal{E}_{\boldsymbol{f}}(\mathcal{B}') \geq \left\|\left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}''\right)-\left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}'\right)\right\|_{L^2}^2

なので、N_0=O_{\tau, X}(1)であることから(エネルギー増加) \mathcal{E}_{\boldsymbol{f}}(\mathcal{B}'')-\mathcal{E}_{\boldsymbol{f}}(\mathcal{B}') \gg_{\tau, X} 1が生じている。

③が成り立っている場合は\mathcal{B}''の代わりにT^{-\mu m}\mathcal{B}''を考えれば、T^{-\mu m}\mathcal{B}''\supset \mathcal{B}'\mathcal{B}''と同じ複雑度を持つ(d-1)-コンパクトな\mathbb{Z}_N上の\sigma-加法族なので、所望の(エネルギー増加) \mathcal{E}_{\boldsymbol{f}}(T^{-\mu m}\mathcal{B}'')-\mathcal{E}_{\boldsymbol{f}}(\mathcal{B}') \gg_{\tau, X} 1が生じている。

\displaystyle \left\|\left.\mathbb{E}\left(T^{\mu m}\left|f_{U^{\perp}}-f_{UAP}\right|\right|\mathcal{B}''\right)-T^{\mu m}\left.\mathbb{E}\left(\left|f_{U^{\perp}}-f_{UAP}\right|\right|\mathcal{B}''\right)\right\|_{L^2} \geq N_0^{-1}

が成り立っている場合は、上記の議論を f_{U^{\perp}} \mapsto \left|f_{U^{\perp}}-f_{UAP}\right|として適用すればよい。 補題の証明終了

補題1より-(k-1)N_0 \leq m \leq (k-1)N_0に対して

\displaystyle \left\|\left.\mathbb{E}\left(T^{\mu m}f_{U^{\perp}}\right|\mathcal{B}''\right)-T^{\mu m}\left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}''\right)\right\|_{L^2} < N_0^{-1}

かつ

\displaystyle \left\|\left.\mathbb{E}\left(T^{\mu m}\left|f_{U^{\perp}}-f_{UAP}\right|\right|\mathcal{B}''\right)-T^{\mu m}\left.\mathbb{E}\left(\left|f_{U^{\perp}}-f_{UAP}\right|\right|\mathcal{B}''\right)\right\|_{L^2} < N_0^{-1}

であると仮定してよい。このとき、Cauchy-Schwarzの不等式によって

\displaystyle \int_{\mathbb{Z}_N}\left|\left.\mathbb{E}\left(T^{\mu m}f_{U^{\perp}}\right|\mathcal{B}''\right)-T^{\mu m}\left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}''\right)\right| \leq \left\|\left.\mathbb{E}\left(T^{\mu m}f_{U^{\perp}}\right|\mathcal{B}''\right)-T^{\mu m}\left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}''\right)\right\|_{L^2} < N_0^{-1}

なので、Markovの不等式によって

\displaystyle \mathbb{P}_{x \in \mathbb{Z}_N}\left(\left|\left.\mathbb{E}\left(T^{\mu m}f_{U^{\perp}}\right|\mathcal{B}''\right)-T^{\mu m}\left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}''\right)\right|(x) \geq \frac{\delta}{4} \right) \ll N_0^{-1} −⑤

が成り立つ。同様にして、

\displaystyle \mathbb{P}_{x \in \mathbb{Z}_N}\left(\left|\left.\mathbb{E}\left(\left|T^{\mu m}f_{U^{\perp}}-T^{\mu m}f_{UAP}\right|\right|\mathcal{B}''\right)-T^{\mu m}\left.\mathbb{E}\left(\left|f_{U^{\perp}}-f_{UAP}\right|\right|\mathcal{B}''\right)\right|(x)\geq \frac{\delta}{32k}\right) \ll N_0^{-1} −⑥.

ここで、n \in \mathbb{Z}_Nに対してE_n''

\displaystyle E_n'':=\left\{x \in \mathbb{Z}_N\left|T^n\left.\mathbb{E}(f_{U^{\perp}}\right|\mathcal{B}'')(x) \geq \frac{3\delta}{4}, \ T^n\left. \mathbb{E}(\left|f_{U^{\perp}}-f_{UAP}\right| \right| \mathcal{B}'')(x) \leq \frac{\delta}{32k}\right\}\right.

と定義する。このとき、各1 \leq \lambda \leq N_0/k_{\ast}に対して

\displaystyle \mathbb{P}_{\mathbb{Z}_N}\left(\bigcap_{m=1}^{k_{\ast}}E_{\mu \lambda m}'\right) \geq \mathbb{P}_{\mathbb{Z}_N}\left(\bigcap_{m=1}^{k_{\ast}}E_{\mu \lambda m}''\right)-O(N_0^{-1}) −⑦

が成り立つ。理由: n \in \mathbb{Z}_Nに対してD_n', \ D_n''

\displaystyle D_n':=\left\{x \in \mathbb{Z}_N \left| \left|\left.\mathbb{E}\left(T^nf_{U^{\perp}}\right|\mathcal{B}''\right)-T^n\left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}''\right)\right|(x) \geq \frac{\delta}{4}\right\}\right.,

\displaystyle D_n'':=\left\{x \in \mathbb{Z}_N \left| \left|\left.\mathbb{E}\left(\left|T^nf_{U^{\perp}}-T^nf_{UAP}\right|\right|\mathcal{B}''\right)-T^n\left.\mathbb{E}\left(\left|f_{U^{\perp}}-f_{UAP}\right|\right|\mathcal{B}''\right)\right|(x) \geq \frac{\delta}{32k}\right\}\right.

と定める。すると、集合の包含関係

\displaystyle \bigcap_{m=1}^{k_{\ast}}E_{\mu \lambda m}'' \setminus \left\{\bigcup_{m=1}^{k_{\ast}}D_{\mu \lambda m}' \cup \bigcup_{m=1}^{k_{\ast}}D_{\mu \lambda m}''\right\} \subset \bigcap_{m=1}^{k_{\ast}}E_{\mu \lambda m}'

が成り立つ。理由: x \in  \bigcap_{m=1}^{k_{\ast}}E_{\mu \lambda m}'' \setminus \left\{\bigcup_{m=1}^{k_{\ast}}D_{\mu \lambda m}' \cup \bigcup_{m=1}^{k_{\ast}}D_{\mu \lambda m}''\right\}であれば、任意の1 \leq m \leq k_{\ast}に対して

\displaystyle T^{\mu \lambda m}\left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}''\right)(x) \geq \frac{3\delta}{4}

及び

\displaystyle \left|\left.\mathbb{E}\left(T^{\mu \lambda m}f_{U^{\perp}}\right|\mathcal{B}''\right)-T^{\mu \lambda m}\left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}''\right)\right|(x) < \frac{\delta}{4}

が成り立つので、三角不等式によって

\begin{align} \left.\mathbb{E}\left(T^{\mu \lambda m}f_{U^{\perp}}\right|\mathcal{B}''\right)(x) &= \left| T^{\mu \lambda m}\left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}''\right)(x) + \left(\left.\mathbb{E}\left(T^{\mu \lambda m}f_{U^{\perp}}\right|\mathcal{B}''\right)(x)-T^{\mu \lambda m}\left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}''\right)(x)\right)\right| \\ &\geq T^{\mu \lambda m}\left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}''\right)(x) - \left|\left.\mathbb{E}\left(T^{\mu \lambda m}f_{U^{\perp}}\right|\mathcal{B}''\right)(x)-T^{\mu \lambda m}\left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}''\right)(x) \right|\\ &> \frac{3\delta}{4}-\frac{\delta}{4} = \frac{\delta}{2}.\end{align}

また、

\displaystyle T^{\mu \lambda m}\left.\mathbb{E}\left(\left|f_{U^{\perp}}-f_{UAP}\right|\right|\mathcal{B}''\right)(x) \leq \frac{\delta}{32k}

及び

\displaystyle \left|\left.\mathbb{E}\left(\left|T^{\mu \lambda m}f_{U^{\perp}}-T^{\mu \lambda m}f_{UAP}\right|\right|\mathcal{B}''\right)-T^{\mu \lambda m}\left.\mathbb{E}\left(\left|f_{U^{\perp}}-f_{UAP}\right|\right|\mathcal{B}''\right)\right|(x) < \frac{\delta}{32k}

が成り立つので、三角不等式によって

\displaystyle \left.\mathbb{E}\left(\left|T^{\mu \lambda m}f_{U^{\perp}}-T^{\mu \lambda m}f_{UAP}\right|\right|\mathcal{B}''\right)(x) < \frac{\delta}{16k}.

故に、x \in  \bigcap_{m=1}^{k_{\ast}}E_{\mu \lambda m}'がわかる 従って、

\displaystyle \#\left(\bigcap_{m=1}^{k_{\ast}}E_{\mu \lambda m}'\right) \geq \#\left(\bigcap_{m=1}^{k_{\ast}}E_{\mu \lambda m}''\right) - \sum_{m=1}^{k_{\ast}}\#D_{\mu \lambda m}'-\sum_{m=1}^{k_{\ast}}\#D_{\mu \lambda m}''

と評価できる。1 \leq \lambda m \leq N_0なので、⑤、⑥より

\displaystyle \mathbb{P}_{\mathbb{Z}_N}(D_{\mu \lambda m}') \ll N_0^{-1}, \ \mathbb{P}_{\mathbb{Z}_N}(D_{\mu \lambda m}'') \ll N_0^{-1}

であり、k_{\ast}=O(1)であることから所望の不等式を得る

ここで、次の性質に注意する: 任意のn \in \mathbb{Z}_Nに対して E_n'' = T^nE_0''が成り立つ。

理由: x \in T^nE_0'' \Longleftrightarrow x+n \in E_0'' \Longleftrightarrow

\displaystyle \left.\mathbb{E}(f_{U^{\perp}}\right|\mathcal{B}'')(x+n) \geq \frac{3\delta}{4}, \ \left. \mathbb{E}(\left|f_{U^{\perp}}-f_{UAP}\right| \right| \mathcal{B}'')(x+n) \leq \frac{\delta}{32k}

\Longleftrightarrow

\displaystyle T^n\left.\mathbb{E}(f_{U^{\perp}}\right|\mathcal{B}'')(x) \geq \frac{3\delta}{4}, \ T^n\left. \mathbb{E}(\left|f_{U^{\perp}}-f_{UAP}\right| \right| \mathcal{B}'')(x) \leq \frac{\delta}{32k}

\Longleftrightarrow x \in E_n'' と確認できる

よって、

\displaystyle \mathbb{P}_{\mathbb{Z}_N}\left(\bigcap_{m=1}^{k_{\ast}}E_{\mu \lambda m}''\right) = \int_{\mathbb{Z}_N}\mathbf{1}_{\bigcap_{m=1}^{k_{\ast}}E_{\mu \lambda m}''} = \int_{\mathbb{Z}_N}\prod_{m=1}^{k_{\ast}}\mathbf{1}_{E_{\mu \lambda m}''} = \int_{\mathbb{Z}_N}\prod_{m=1}^{k_{\ast}}T^{\mu \lambda m}\mathbf{1}_{E_0''}

が成り立ち、②、⑦より

\displaystyle \mathbb{P}_{\mathbb{Z}_N}\left( \bigcap_{m=1}^{k_{\ast}}E_{\mu \lambda m}\right) \geq \int_{\mathbb{Z}_N}\prod_{m=1}^{k_{\ast}}T^{\mu \lambda m}\mathbf{1}_{E_0''} - O(N_0^{-1})

が得られる。従って、前記事⑤より

\displaystyle \mathbb{E}_{1 \leq r \leq N_0}\left(\int_{\mathbb{Z}_N}\prod_{j=0}^{k-1}T^{\mu jr}f_{U^{\perp}}\right) \gg \mathbb{E}_{1 \leq \lambda \leq \frac{N_0}{k_{\ast}}}\left(\int_{\mathbb{Z}_N}\prod_{m=1}^{k_{\ast}}T^{\mu \lambda m}\mathbf{1}_{E_0''}\right) - O(N_0^{-1}) −⑧

が示された。定義より\mathbf{1}_{E_0''}\mathcal{B}''-可測関数なので、(この証明の最後の方法により)帰納法の仮定を使える状況になっている。しかしながら、\mathcal{B}''の複雑度がX'に依存していることから(成功)には至らない。そこで、E_0''をもっと小さくする。\widetilde{E}

\displaystyle \widetilde{E} := \left\{x \in \mathbb{Z}_N\left| \left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}\right) \geq \frac{7\delta}{8}, \ \left.\mathbb{E}\left(\left|f_{U^{\perp}}-f_{UAP}\right|\right|\mathcal{B}\right) \leq \frac{\delta}{64k}\right\}\right.

と定める。

補題2 (Lemma 10.4) (エネルギー増加)が生じるか
\displaystyle \mathbb{P}_{\mathbb{Z}_N}\left(\widetilde{E}\setminus E_0''\right) \ll \tau^2, \ \mathbb{P}_{\mathbb{Z}_N}\left(E_0''\cap \widetilde{E}\right) \geq \frac{\delta}{32}
のどちらかが必ず成立する。

証明. \mathcal{E}_{\boldsymbol{f}}(\mathcal{B}'')-\mathcal{E}_{\boldsymbol{f}}(\mathcal{B}') \leq \tau^2 と仮定してよい(そうでなければ(エネルギー増加)が生じている)。もともと\mathcal{E}_{\boldsymbol{f}}(\mathcal{B}')-\mathcal{E}_{\boldsymbol{f}}(\mathcal{B}) \leq \tau^2 と仮定しているので

\mathcal{E}_{\boldsymbol{f}}(\mathcal{B}'')-\mathcal{E}_{\boldsymbol{f}}(\mathcal{B}) \leq 2\tau^2

が成り立つ。すると、§7のエネルギーギャップ公式より

\displaystyle \int_{\mathbb{Z}_N}\left|\left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}''\right)-\left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}\right)\right|^2 \leq 2\tau^2

及び

\displaystyle \int_{\mathbb{Z}_N}\left|\left.\mathbb{E}\left(\left|f_{U^{\perp}}-f_{UAP}\right|\right|\mathcal{B}''\right)-\left.\mathbb{E}\left(\left|f_{U^{\perp}}-f_{UAP}\right|\right|\mathcal{B}\right)\right|^2 \leq 2\tau^2

が成り立つ。これらにChebyshevの不等式を用いると

\displaystyle \mathbb{P}_{x \in \mathbb{Z}_N}\left(\left|\left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}''\right)-\left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}\right)\right|(x) \geq \frac{\delta}{8}\right) \ll \tau^2 −⑨

及び

\displaystyle \mathbb{P}_{x \in \mathbb{Z}_N}\left(\left|\left.\mathbb{E}\left(\left|f_{U^{\perp}}-f_{UAP}\right|\right|\mathcal{B}''\right)-\left.\mathbb{E}\left(\left|f_{U^{\perp}}-f_{UAP}\right|\right|\mathcal{B}\right)\right|(x) \geq \frac{\delta}{64k}\right) \ll \tau^2 −⑩

が得られる。x \in \widetilde{E}\setminus E_0''とすると、

\displaystyle \left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}\right)(x) \geq \frac{7\delta}{8}, \ \left.\mathbb{E}\left(\left|f_{U^{\perp}}-f_{UAP}\right|\right|\mathcal{B}\right)(x) \leq \frac{\delta}{64k}

が成り立ち、更に

\displaystyle \left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}''\right)(x) < \frac{3\delta}{4} −⑪

または

\displaystyle\left.\mathbb{E}\left(\left|f_{U^{\perp}}-f_{UAP}\right|\right|\mathcal{B}''\right)(x) > \frac{\delta}{32k} −⑫

が成り立つ。⑪が成り立つときは、三角不等式より

\displaystyle \left|\left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}''\right)-\left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}\right)\right|(x) > \frac{\delta}{8}

となり、⑫が成り立つときは

\displaystyle \left|\left.\mathbb{E}\left(\left|f_{U^{\perp}}-f_{UAP}\right|\right|\mathcal{B}''\right)-\left.\mathbb{E}\left(\left|f_{U^{\perp}}-f_{UAP}\right|\right|\mathcal{B}\right)\right|(x) > \frac{\delta}{64k}

となる。従って、⑨、⑩より \mathbb{P}_{\mathbb{Z}_N}\left(\widetilde{E}\setminus E_0''\right) \ll \tau^2 が成り立つことが示された。

もう一つの不等式を証明する。仮定より

\displaystyle \int_{\mathbb{Z}_N}\left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}\right) = \int_{\mathbb{Z}_N}f_{U^{\perp}} \geq \delta

なので、N \gg 1

\displaystyle \mathbb{P}_{x \in \mathbb{Z}_N}\left(\left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}\right)(x) \geq \frac{7\delta}{8}\right) \geq \frac{\delta}{8}

が成り立つ。理由: 背理法で証明する。

\displaystyle \mathbb{P}_{x \in \mathbb{Z}_N}\left(\left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}\right)(x) \geq \frac{7\delta}{8}\right) < \frac{\delta}{8}

と仮定すると

\displaystyle \mathbb{P}_{x \in \mathbb{Z}_N}\left(\left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}\right)(x) < \frac{7\delta}{8}\right) \geq 1-\frac{\delta}{8}

となる。\left(1-\frac{\delta}{8}\right)Nが整数であれば

\displaystyle \#\left\{x \in \mathbb{Z}_N\left| \left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}\right)(x) < \frac{7\delta}{8} \right\}\right. \geq \left(1-\frac{\delta}{8}\right) N

なので、\left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}\right)が有界関数であることに注意して

\displaystyle \sum_{x=1}^N\left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}\right)(x) < \frac{\delta}{8}N+\left(1-\frac{\delta}{8}\right)N \times \frac{7\delta}{8} =\left(\delta-\frac{7\delta^2}{64}\right)N < \delta N

となり、

\displaystyle \int_{\mathbb{Z}_N}\left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}\right)  < \delta

となって矛盾する。\left(1-\frac{\delta}{8}\right)Nが整数でなければ

\displaystyle \#\left\{x \in \mathbb{Z}_N\left| \left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}\right) < \frac{7\delta}{8} \right\}\right. \geq \left[\left(1-\frac{\delta}{8}\right) N\right]+1

であり、N-\left(\left[\left(1-\frac{\delta}{8}\right) N\right]+1\right) < \frac{\delta}{8}N なので

\displaystyle \sum_{x=1}^N\left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}\right)(x) < \frac{\delta}{8}N+\left\{\left(1-\frac{\delta}{8}\right)N+1\right\} \times \frac{7\delta}{8} =\delta N -\frac{7\delta^2}{64}N+\frac{7\delta}{8}

となり、N \gg 1であれば

\displaystyle \int_{\mathbb{Z}_N}\left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}\right)  < \delta-\frac{7\delta^2}{64}+\frac{7\delta}{8N} < \delta

となって矛盾する

仮定1. とCauchy-Schwarzの不等式より

\displaystyle \int_{\mathbb{Z}_N}\left.\mathbb{E}\left(\left|f_{U^{\perp}}-f_{UAP}\right|\right|\mathcal{B}\right) = \int_{\mathbb{Z}_N}\left|f_{U^{\perp}}-f_{UAP}\right|\leq \left\|f_{U^{\perp}}-f_{UAP}\right\|_{L^2}\leq \frac{\delta^2}{1024k}

なので、Markovの不等式より

\displaystyle \mathbb{P}_{x \in \mathbb{Z}_N}\left(\left.\mathbb{E}\left(\left|f_{U^{\perp}}-f_{UAP}\right|\right|\mathcal{B}\right)(x) > \frac{\delta}{64 k}\right) \leq \frac{64k}{\delta}\times \frac{\delta^2}{1024k} = \frac{\delta}{16}

が得られる。こうして、

\begin{align} \mathbb{P}_{\mathbb{Z}_N}\left(\widetilde{E}\right) &\geq \mathbb{P}_{x \in \mathbb{Z}_N}\left(\left.\mathbb{E}\left(f_{U^{\perp}}\right|\mathcal{B}\right)(x) \geq \frac{7\delta}{8}\right)-\mathbb{P}_{x \in \mathbb{Z}_N}\left(\left.\mathbb{E}\left(\left|f_{U^{\perp}}-f_{UAP}\right|\right|\mathcal{B}\right)(x) > \frac{\delta}{64 k}\right) \\ &\geq \frac{\delta}{8}-\frac{\delta}{16}=\frac{\delta}{16}\end{align}

となり、\displaystyle E_0'' \cap \widetilde{E}  = \widetilde{E}\setminus \left(\widetilde{E}\setminus E_0''\right) なので、

\displaystyle \mathbb{P}_{\mathbb{Z}_N}\left(E_0''\cap \widetilde{E}\right) \geq \mathbb{P}_{\mathbb{Z}_N}\left(\widetilde{E}\right)-\mathbb{P}_{\mathbb{Z}_N}\left(\widetilde{E}\setminus E_0''\right) \geq \frac{\delta}{16}-O(\tau^2)

を得る。\tau \ll 1なので、\displaystyle \mathbb{P}_{\mathbb{Z}_N}\left(E_0''\cap \widetilde{E}\right) \geq \frac{\delta}{32} と結論づけられる。 補題の証明終了

補題2より

\displaystyle \mathbb{P}_{\mathbb{Z}_N}\left(\widetilde{E}\setminus E_0''\right) \ll \tau^2, \ \mathbb{P}_{\mathbb{Z}_N}\left(E_0''\cap \widetilde{E}\right) \geq \frac{\delta}{32}

の場合を考えればよい。このとき、

\displaystyle \left\|\mathbf{1}_{E_0''\cap \widetilde{E}}-\mathbf{1}_{\widetilde{E}}\right\|_{L^2} \ll \tau

が成り立つ。理由: 補題2の最後の式変形より

\begin{align} \mathbb{P}_{\mathbb{Z}_N}\left(\widetilde{E}\setminus E_0''\right) &\geq \mathbb{P}_{\mathbb{Z}_N}\left(\widetilde{E}\right)-\mathbb{P}_{\mathbb{Z}_N}\left(E_0''\cap \widetilde{E}\right) = \int_{\mathbb{Z}_N}\mathbf{1}_{\widetilde{E}}-\int_{\mathbb{Z}_N}\mathbf{1}_{E_0''\cap \widetilde{E}} \\
&= \int_{\mathbb{Z}_N}\left|\mathbf{1}_{\widetilde{E}}-\mathbf{1}_{E_0''\cap \widetilde{E}}\right|^2 = \left\|\mathbf{1}_{\widetilde{E}}-\mathbf{1}_{E_0''\cap \widetilde{E}}\right\|_{L^2}^2\end{align}

と計算できることからわかる

定義から\widetilde{E} \in \mathcal{B}であり、\mathbf{1}_{\widetilde{E}}\mathcal{B}-可測関数。\mathcal{B}(d-1)-コンパクトな\mathbb{Z}_N上の\sigma-加法族で複雑度は高々Xである。よって、§6(その三)より非負値有界な一様概周期関数 \widetilde{f}_{UAP} \in UAP^{d-1}であって

\displaystyle \left\|\mathbf{1}_{\widetilde{E}}-\widetilde{f}_{UAP}\right\|_{L^2}\ll \tau, \quad \left\|\widetilde{f}_{UAP}\right\|_{UAP^{d-1}} \ll_{X, \tau} 1

を満たすものを取れる。すると、三角不等式によって

\displaystyle \left\|\mathbf{1}_{E_0''\cap \widetilde{E}}-\widetilde{f}_{UAP}\right\|_{L^2}\ll \tau

であり、

\displaystyle \int_{\mathbb{Z}_N}\mathbf{1}_{E_0''\cap \widetilde{E}} = \mathbb{P}_{\mathbb{Z}_N}\left(E_0''\cap \widetilde{E}\right) \geq \frac{\delta}{32}

である。そこで、

\displaystyle \left\|\mathbf{1}_{E_0''\cap \widetilde{E}}-\widetilde{f}_{UAP}\right\|_{L^2} = O(\tau) \leq \frac{(\delta/32)^2}{1024k_{\ast}}

が成り立つだけ\tauを小さくとっておけば、Thm 3.3の主張において

\displaystyle  f_{U^{\perp}}\mapsto \mathbf{1}_{E_0''\cap \widetilde{E}}, \quad \delta \mapsto \frac{\delta}{32}, \quad f_{UAP} \mapsto \widetilde{f}_{UAP},\quad M \mapsto O_{X, \tau}(1), \quad k \mapsto k_{\ast}, \quad d \mapsto d-1

として帰納法の仮定を適用することができる。その帰結として

\displaystyle \mathbb{E}_{1 \leq \lambda \leq \frac{N_0}{k_{\ast}}}\left(\int_{\mathbb{Z}_N}\prod_{m=1}^{k_{\ast}}T^{\mu \lambda m}\mathbf{1}_{E_0'' \cap \widetilde{E}}\right) \gg_{\tau, X} 1

が得られる。注意: 帰納法の仮定からは直接的には

\displaystyle \mathbb{E}_{0 \leq \lambda \leq \frac{N_0}{k_{\ast}}}\left(\int_{\mathbb{Z}_N}\prod_{m=0}^{k_{\ast}-1}T^{\mu \lambda m}\mathbf{1}_{E_0'' \cap \widetilde{E}}\right) \gg_{\tau, X} 1

が得られるが、

\begin{align} &\left(\left[\frac{N_0}{k_{\ast}}\right]+1\right)\mathbb{E}_{0 \leq \lambda \leq \frac{N_0}{k_{\ast}}}\left(\int_{\mathbb{Z}_N}\prod_{m=0}^{k_{\ast}-1}T^{\mu \lambda m}\mathbf{1}_{E_0'' \cap \widetilde{E}}\right) \\ 
&= \left[\frac{N_0}{k_{\ast}}\right]\mathbb{E}_{1 \leq \lambda \leq \frac{N_0}{k_{\ast}}}\left(\int_{\mathbb{Z}_N}\prod_{m=0}^{k_{\ast}-1}T^{\mu \lambda m}\mathbf{1}_{E_0'' \cap \widetilde{E}}\right)+\int_{\mathbb{Z}_N}\left(\mathbf{1}_{E_0''\cap \widetilde{E}}\right)^{k_{\ast}} \\
&\leq \left[\frac{N_0}{k_{\ast}}\right]\mathbb{E}_{1 \leq \lambda \leq \frac{N_0}{k_{\ast}}}\left(\int_{\mathbb{Z}_N}\prod_{m=0}^{k_{\ast}-1}T^{\mu \lambda m}\mathbf{1}_{E_0'' \cap \widetilde{E}}\right)+1\end{align}

より

\displaystyle \mathbb{E}_{1 \leq \lambda \leq \frac{N_0}{k_{\ast}}}\left(\int_{\mathbb{Z}_N}\prod_{m=0}^{k_{\ast}-1}T^{\mu \lambda m}\mathbf{1}_{E_0'' \cap \widetilde{E}}\right) \geq \mathbb{E}_{0 \leq \lambda \leq \frac{N_0}{k_{\ast}}}\left(\int_{\mathbb{Z}_N}\prod_{m=0}^{k_{\ast}-1}T^{\mu \lambda m}\mathbf{1}_{E_0'' \cap \widetilde{E}}\right)-\left[\frac{N_0}{k_{\ast}}\right]^{-1}

なので、N_0 \gg_{\tau, X} 1に対して

\displaystyle \mathbb{E}_{1 \leq \lambda \leq \frac{N_0}{k_{\ast}}}\left(\int_{\mathbb{Z}_N}\prod_{m=0}^{k_{\ast}-1}T^{\mu \lambda m}\mathbf{1}_{E_0'' \cap \widetilde{E}}\right) \gg_{\tau, X} 1

が成り立つ。そして、積分のシフト不変性とシフト作用素の基本性質から

\begin{align} &\mathbb{E}_{1 \leq \lambda \leq \frac{N_0}{k_{\ast}}}\left(\int_{\mathbb{Z}_N}\prod_{m=0}^{k_{\ast}-1}T^{\mu \lambda m}\mathbf{1}_{E_0'' \cap \widetilde{E}}\right)
\\ &=\mathbb{E}_{1 \leq \lambda \leq \frac{N_0}{k_{\ast}}}\left(\int_{\mathbb{Z}_N}\prod_{m=0}^{k_{\ast}-1}T^{\mu \lambda (m+1)}\mathbf{1}_{E_0'' \cap \widetilde{E}}\right)=\mathbb{E}_{1 \leq \lambda \leq \frac{N_0}{k_{\ast}}}\left(\int_{\mathbb{Z}_N}\prod_{m=1}^{k_{\ast}}T^{\mu \lambda m}\mathbf{1}_{E_0'' \cap \widetilde{E}}\right)\end{align}

である よって、前記事(⭐︎)及び⑧より、或る定数C > 0, \ c(\tau, X) > 0が存在して

\begin{align} \mathbb{E}_{0 \leq r \leq N_1} \left( \int_{\mathbb{Z}_N}\prod_{j=0}^{k-1}T^{jr}f_{U^{\perp}}\right) &\gg_{N_0}\mathbb{E}_{1 \leq \mu \leq \frac{N_1}{N_0}}\left( \mathbb{E}_{1 \leq r \leq N_0} \left( \int_{\mathbb{Z}_N}\prod_{j=0}^{k-1}T^{\mu jr}f_{U^{\perp}}\right) \right)\\
&\gg \mathbb{E}_{1 \leq \mu \leq \frac{N_1}{N_0}}\left(\mathbb{E}_{1 \leq \lambda \leq \frac{N_0}{k_{\ast}}}\left(\int_{\mathbb{Z}_N}\prod_{m=1}^{k_{\ast}}T^{\mu \lambda m}\mathbf{1}_{E_0''}\right)\right) - CN_0^{-1}\\
&\geq \mathbb{E}_{1 \leq \mu \leq \frac{N_1}{N_0}}\left(\mathbb{E}_{1 \leq \lambda \leq \frac{N_0}{k_{\ast}}}\left(\int_{\mathbb{Z}_N}\prod_{m=1}^{k_{\ast}}T^{\mu \lambda m}\mathbf{1}_{E_0''\cap \widetilde{E}}\right)\right) - CN_0^{-1}\\
&\geq c(\tau, X)-CN_0^{-1}\end{align}

と評価できる。そこで、N_0=N_0(\tau, X)N_0 > \frac{C}{c(\tau, X)}を満たすようにとっておけば

\displaystyle \mathbb{E}_{0 \leq r \leq N_1} \left( \int_{\mathbb{Z}_N}\prod_{j=0}^{k-1}T^{jr}f_{U^{\perp}}\right) \gg_{\tau, X} 1

が得られる。これは回帰定理ダイコトミーの証明の完了を宣言している。 Q.E.D.


以上でSzemerédiの定理は完全に証明されました。それではGreen-Taoの論文に移りましょう。

*1:このようにN_0以下の値にしか適用しないのに (k-1)N_0以下で成り立つように準備をしている箇所がある。

*2:積分のシフト不変性から従う。