インテジャーズ

INTEGERS

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

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

Taoの論文の最終節: §10 Recurrence for almost periodic functions に入ります。Szemerédiの定理の証明で残っているのは

(再掲) 一様概周期関数の回帰性 (Theorem 3.3) d \geq 0, k\geq 1を整数とする。非負値有界関数 f_{U^{\perp}}, f_{UAP}は或る 0 < \delta \leq 1, M > 0に対して
1. \displaystyle \left\| f_{U^{\perp}}-f_{UAP} \right\|_{L^2} \leq \frac{\delta^2}{1024k},\quad 2. \displaystyle \int_{\mathbb{Z}_N}f_{U^{\perp}} \geq \delta,\quad 3. \left\|f_{UAP}\right\|_{UAP^d} < M
を満たすと仮定する。このとき、任意の\mu \in \mathbb{Z}_N及び正整数N_1に対して
\displaystyle \mathbb{E}_{0 \leq r \leq N_1}\left( \int_{\mathbb{Z}_N}\prod_{j=0}^{k-1}T^{\mu jr}f_{U^{\perp}}\right) \gg_{d, k, \delta, M} 1
が成り立つ。

ですが、§9でKeyとなる命題(Prop 9.1)を証明し、Thm 3.3のd=0, 1の場合の証明を済ませました。d \geq 2の場合はProp 9.1を即座には適用することができないため、この節においてProp 9.1を上手く適用できるように工夫して証明されます。

まず、Thm 3.3は\mu = 1の場合に示せば十分であることを確認します。理由: \mu =0のときはHölderの不等式より

\displaystyle \int_{\mathbb{Z}_N}f_{U^{\perp}}^k \geq \left( \int_{\mathbb{Z}_N}f_{U^{\perp}}\right)^k \geq \delta^k

となって主張が成立する。\mu \ne 0のときは、L^2-ノルム、積分、一様概周期性ノルムがいずれもスケール不変であることに注意すれば f_{U^{\perp}} \mapsto (f_{U^{\perp}})_{\mu^{-1}}, f_{UAP}\mapsto (f_{UAP})_{\mu^{-1}}と置き換えることができ、

\displaystyle T^{jr}(f_{U^{\perp}})_{\mu^{-1}}(x) = f_{U^{\perp}}(\mu(x+jr))=T^{\mu jr}f_{U^{\perp}}(\mu x)

であることと、\mu倍写像の全単射性から\mu = 1の場合に帰着できることがわかる

Thm 3.3をdに関する帰納法で証明しますが、d-1のときに成立すると仮定してdの場合を証明するのに§7のエネルギー増加法を利用します。従って、実際に証明すべきことは次の命題に集約されます。ただし、次の略記ルールを適用します:

略記 以下、パラメータd, k, \delta, Mについては依存していもそのことを明記しない。このルールはLandau(Vinogradov)の記号における定数についても同様である。

命題 (回帰定理ダイコトミー) d2以上の整数とし、d-1に対してはThm 3.3が証明されていると仮定する。非負値有界関数 f_{U^{\perp}}, f_{UAP}は或る 0 < \delta \leq 1, M > 0に対して

1. \displaystyle \left\| f_{U^{\perp}}-f_{UAP} \right\|_{L^2} \leq \frac{\delta^2}{1024k},\quad 2. \displaystyle \int_{\mathbb{Z}_N}f_{U^{\perp}} \geq \delta,\quad 3. \left\|f_{UAP}\right\|_{UAP^d} < M

を満たすと仮定する。\boldsymbol{f} \in \mathrm{Map}(\mathbb{Z}_N, \mathbb{C})^2

\displaystyle \boldsymbol{f} = (f_{U^{\perp}}, \left|f_{U^{\perp}}-f_{UAP}\right|)

とする。また、X, \ X' \geq 0は整数で、\mathcal{B} (resp. \mathcal{B}')をそれぞれ複雑度がX (resp. X')以下であるような(d-1)-コンパクトな\mathbb{Z}_N上の\sigma-加法族であって \mathcal{B} \subset \mathcal{B}' 及び \tau \ll 1に対するエネルギーギャップ条件

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

を満たすようなものとする。このとき、次の少なくとも一方を満たす:

(成功): 任意の整数N_1\geq 0に対して

\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

が成り立つ。

(エネルギー増加): 或る複雑度がO_{\tau, X, X'}(1)(d-1)-コンパクトな\mathbb{Z}_N上の\sigma-加法族 \mathcal{B}'' \supset \mathcal{B}'が存在して、エネルギー増加

\displaystyle \mathcal{E}_{\boldsymbol{f}}(\mathcal{B}'')-\mathcal{E}_{\boldsymbol{f}}(\mathcal{B}') \gg_{\tau, X} 1

が生じる。

回帰定理ダイコトミー \Longrightarrow Thm 3.3の証明

回帰定理ダイコトミーが証明されれば(直後に少し詳しく解説するが)、§7のエネルギー増加法によって帰納法のステップd-1 \mapsto dの証明が完了し(\mu=1の場合を示せば一般でも成り立つことは既にみた)、§9でd=0, 1の場合を証明していることと合わせて、Thm 3.3が証明されたことになる。エネルギー増加法の適用については、§7補題のP(M)のパラメータMとThm 3.3に現れるMは異なることに注意*1。そこで、M \mapsto Cとして、P(C)はここでは不等式

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

が成り立つことである。\boldsymbol{f}の各成分が有界関数である必要があるが、それは f_{U^{\perp}}, \ f_{UAP}が非負値有界であることから従う。§8で既に言及したように各部分で依存するパラメータを増やしても帰結が同じパラメータに依存するようになるだけなので、d, k, \delta, M依存を省略していることから(\tauについても実際は\tau=O_{d, k, \delta, M}(1)であり、§7の補題におけるmm=2)、エネルギー増加法による帰結は

\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_{d, k, \delta, M} 1

となる。 Q.E.D.


以下、途中で幾つかの補題を証明する、入れ子方式で証明していきます。(その一)ではProp 9.1を適用するところまで書いて、(その二)で完結させます。

回帰定理ダイコトミーの証明

\left\|f_{UAP}\right\|_{UAP^d} < Mであることから、空でない有限集合Hn \in \mathbb{Z}_N, h \in H毎に定義される有界関数c_{n, h} \in B(UAP^{d-1})h \in H毎に定義される有界関数g_hが存在して、任意のn \in \mathbb{Z}_Nに対して

\displaystyle T^nf_{UAP}=M\mathbb{E}_{h \in H}(c_{n, h}g_h) −①

が成り立つ。N_0=N_0(\tau, X)\tau, Xのみに依存して定まる或る整数とする(取り方は最後に説明する)。

N_1 \leq N_0のときは

\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

が成り立つ。理由: f_{U^{\perp}}が非負値なので、r=0の部分をみて

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

と評価でき、Hölderの不等式より

\displaystyle \int_{\mathbb{Z}_N}\left(f_{U^{\perp}}\right)^k \geq \left( \int_{\mathbb{Z}_N}f_{U^{\perp}}\right)^k \geq \delta^k

なので、

\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_{N_0} 1

を得る つまり、(成功)となるので、以下、N_1 > N_0の場合を考える。このとき、

\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_{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) −(⭐︎)

が成り立つ。理由:1 \leq r \leq N_0に対して、1 \leq r' \leq N_0 及び 1 \leq \mu \leq N_1/N_0 を用いて r=\mu r'と表す方法は高々O_{N_0}(1)通りなので

\begin{align} &O_{N_0}(1)(N_1+1)\left( \mathbb{E}_{0 \leq r \leq N_1} \left( \int_{\mathbb{Z}_N}\prod_{j=0}^{k-1}T^{jr}f_{U^{\perp}}\right)\right) \\ &\geq O_{N_0}(1)N_1\left( \mathbb{E}_{1 \leq r \leq N_1} \left( \int_{\mathbb{Z}_N}\prod_{j=0}^{k-1}T^{jr}f_{U^{\perp}}\right)\right) \\ &\geq \left[ \frac{N_1}{N_0}\right] \times \left[ N_0 \right] \left( \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) \right)\end{align}

が成り立つ。両辺をN_1で割ることにより

\displaystyle O_{N_0}(1)\left(  \mathbb{E}_{0 \leq r \leq N_1} \left( \int_{\mathbb{Z}_N}\prod_{j=0}^{k-1}T^{jr}f_{U^{\perp}}\right) \right) \geq \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)

を得る そこで、1 \leq \mu \leq N_1/N_0 を固定して

\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)

について考察する。

補題 (有限ランク近似, Lemma 10.2) h_1, \dots, h_{N_0^4} \in H が存在して*2、任意の0 \leq m \leq (k-1)N_0に対して
\displaystyle \left\| \mathbb{E}_{h \in H}(c_{\mu m, h}g_h)-\mathbb{E}_{1 \leq j \leq N_0^4}(c_{\mu m, h_j}g_{h_j}) \right\|_{L^2} \ll N_0^{-1}
が成り立つ。

補題の証明

0 \leq m \leq (k-1)N_0を固定し、D:=N_0^4, G_h=G_h(m):=c_{\mu m, h}g_h \ (h \in H), F=F(m):=\mathbb{E}_{h \in H}(G_h)とする。以下、\boldsymbol{h}=(h_1, \dots, h_D)という略記を用いる。

\displaystyle \mathbb{P}_{\boldsymbol{h} \in H^D}\left(\left\|F-\mathbb{E}_{1 \leq j \leq D}(G_{h_j})\right\|_{L^2} \geq \frac{\sqrt{kN_0}}{N_0^2}\right) \leq \frac{1}{kN_0} –②

を示せばよい。理由: 集合\mathcal{F}_m

\displaystyle \mathcal{F}_m := \left\{ \boldsymbol{h} \in H^D \left| \left\|F(m)-\mathbb{E}_{1 \leq j \leq D}(G_{h_j}(m))\right\|_{L^2} < \frac{\sqrt{kN_0}}{N_0^2}\right\}\right.,

\mathcal{G}_m

\displaystyle \mathcal{G}_m := \left\{ \boldsymbol{h} \in H^D \left| \left\|F(m)-\mathbb{E}_{1 \leq j \leq D}(G_{h_j}(m))\right\|_{L^2} \geq \frac{\sqrt{kN_0}}{N_0^2}\right\}\right.

とする。

\displaystyle \mathbb{P}_{H^D}\left( \bigcap_{m=0}^{(k-1)N_0}\mathcal{F}_m\right)= 1 - \mathbb{P}_{H^D}\left(\bigcup_{m=0}^{(k-1)N_0}\mathcal{G}_m\right)

であり

\displaystyle \mathbb{P}_{H^D}\left( \bigcup_{m=0}^{(k-1)N_0}\mathcal{G}_m\right) \leq \sum_{m=0}^{(k-1)N_0}\mathbb{P}_{H^D}(\mathcal{G}_m)

なので、不等式②が示されれば

\displaystyle \mathbb{P}_{H^D}\left( \bigcap_{m=0}^{(k-1)N_0}\mathcal{F}_m\right) \geq 1-\frac{(k-1)N_0+1}{kN_0} > 0

となって、\displaystyle \bigcap_{m=0}^{(k-1)N_0}\mathcal{F}_m の元が存在することがわかる(\displaystyle \sqrt{kN_0}/N_0^2 \ll N_0^{-1}に注意)

不等式②を示すには

\displaystyle \mathbb{E}_{\boldsymbol{h} \in H^D}\left( \left\|F-\mathbb{E}_{1 \leq j \leq D}(G_{h_j})\right\|_{L^2}^2\right) \leq \frac{1}{D}

を示せばよい。理由: Chebyshevの不等式*3より、この不等式が証明されれば

\begin{align} &\mathbb{P}_{\boldsymbol{h} \in H^D}\left(\left\|F-\mathbb{E}_{1 \leq j \leq D}(G_{h_j})\right\|_{L^2} \geq \frac{\sqrt{kN_0}}{N_0^2}\right) \\ &\leq \frac{1}{\frac{kN_0}{N_0^4}}\times  \mathbb{E}_{\boldsymbol{h} \in H^D}\left( \left\|F-\mathbb{E}_{1 \leq j \leq D}(G_{h_j})\right\|_{L^2}^2\right) \leq \frac{D}{kN_0}\times \frac{1}{D} = \frac{1}{kN_0}\end{align}

と不等式②が得られる

まず、L^2-ノルムの二乗を展開して

\displaystyle \mathbb{E}_{\boldsymbol{h} \in H^D}\left( \left\|F-\mathbb{E}_{1 \leq j \leq D}(G_{h_j})\right\|_{L^2}^2\right) = \mathbb{E}_{\boldsymbol{h} \in H^D}\left( \int_{\mathbb{Z}_N}\left\{\left|F\right|^2-2\mathrm{Re}\left( \mathbb{E}_{1 \leq j \leq D}(\overline{F}G_{h_j})\right)+\left|\mathbb{E}_{1 \leq j \leq D}(G_{h_j})\right|^2\right\} \right).

\displaystyle \left|\mathbb{E}_{1 \leq j \leq D}(G_{h_j})\right|^2 = \left(\mathbb{E}_{1 \leq j \leq D}(G_{h_j})\right) \left(\mathbb{E}_{1 \leq j' \leq D}(\overline{G_{h_j'}})\right)=\mathbb{E}_{1 \leq j, j' \leq D}\left(\overline{G_{h_{j'}}}G_{h_j}\right)

に注意して、和の順序を入れ替えると

\begin{align} &\mathbb{E}_{\boldsymbol{h} \in H^D}\left( \left\|F-\mathbb{E}_{1 \leq j \leq D}(G_{h_j})\right\|_{L^2}^2\right) \\ &= \left\|F\right\|_{L^2}^2-2\mathrm{Re}\left(\mathbb{E}_{1 \leq j \leq D}\left( \int_{\mathbb{Z}_N}\overline{F}\mathbb{E}_{\boldsymbol{h} \in H}(G_{h_j})\right)\right) + \mathbb{E}_{1 \leq j, j' \leq D}\left( \int_{\mathbb{Z}_N}\mathbb{E}_{\boldsymbol{h} \in H}\left(\overline{G_{h_{j'}}}G_{h_j}\right)\right)\end{align}

と計算できる。ここで、各1 \leq j \leq Dに対して

\mathbb{E}_{\boldsymbol{h} \in H^D}(G_{h_j}) = \mathbb{E}_{h \in H}(G_h) = F

である。理由:

\displaystyle \mathbb{E}_{\boldsymbol{h} \in H}(G_{h_j}) = \sum_{(h_1, \dots, h_D) \in H^D}\frac{G_{h_j}}{(\#H)^D} = \sum_{h \in H}\frac{G_h}{(\#H)^D}\sum_{(h_1, \dots, h_{j-1}, h, h_{j+1}, \dots, h_D) \in H^D}1=\sum_{h \in H}\frac{G_h}{\#H}= F

と計算される

また、1 \leq j \neq j' \leq Dに対して

\mathbb{E}_{\boldsymbol{h} \in H^D}\left(\overline{G_{h_{j'}}}G_{h_j}\right) = \left|F\right|^2

である。理由: (j < j'として記述する。)

\begin{align} \mathbb{E}_{\boldsymbol{h} \in H^D}\left(\overline{G_{h_{j'}}}G_{h_j}\right) &= \sum_{(h_1, \dots, h_D) \in H^D}\frac{\overline{G_{h_{j'}}}G_{h_j}}{(\#H)^D} = \sum_{h, h' \in H}\frac{\overline{G_{h'}}G_h}{(\#H)^D}\sum_{(h_1, \dots, h_{j-1}, h, h_{j+1}, \dots, h_{j'-1}, h', h_{j'+1}, \dots, h_D)\in H^D}1 \\ &= \sum_{h, h' \in H}\frac{\overline{G_{h'}}G_h}{(\#H)^2} = \bigl(\mathbb{E}_{h' \in H}(\overline{G_{h'}})\bigr)\bigl( \mathbb{E}_{h \in H}(G_h)\bigr) = \left|F\right|^2\end{align}

と計算される 従って、

\begin{align}&\mathbb{E}_{\boldsymbol{h} \in H^D}\left( \left\|F-\mathbb{E}_{1 \leq j \leq D}(G_{h_j})\right\|_{L^2}^2\right) \\ &= \left\|F\right\|_{L^2}^2-2\left\|F\right\|_{L^2}^2+\mathbb{E}_{1 \leq j, j' \leq D}\left( \delta_{j, j'}\int_{\mathbb{Z}_N}\mathbb{E}_{\boldsymbol{h} \in H^D}\left(\overline{G_{h_{j'}}}G_{h_j}\right)+(1-\delta_{j, j'})\int_{\mathbb{Z}_N}\left|F\right|^2\right) \\ &= \mathbb{E}_{1 \leq j, j' \leq D}\left( \delta_{j, j'}\int_{\mathbb{Z}_N}\left(\mathbb{E}_{\boldsymbol{h} \in H^D}\left(\overline{G_{h_{j'}}}G_{h_j}\right)-\left|F\right|^2\right)\right)\end{align}


を得る(\delta_{j, j'}はKroneckerのデルタ)。G_hが有界関数であることに注意すれば、j=j'のとき

\displaystyle \mathbb{E}_{\boldsymbol{h} \in H^D}\left(\overline{G_{h_{j'}}}G_{h_j}\right)-\left|F\right|^2 \leq \mathbb{E}_{\boldsymbol{h} \in H^D}\left(\left|G_{h_j}\right|^2\right) \leq 1

と評価できるので、

\displaystyle \mathbb{E}_{\boldsymbol{h} \in H^D}\left( \left\|F-\mathbb{E}_{1 \leq j \leq D}(G_{h_j})\right\|_{L^2}^2\right) \leq \mathbb{E}_{1 \leq j, j' \leq D}(\delta_{j, j'}) = \frac{1}{D}

が示された。 補題の証明終了

補題によって存在するh_1, \dots, h_{N_0^4}をとって固定する。すると、①と補題より任意の0 \leq m \leq (k-1)N_0に対して

\displaystyle \left\|T^{\mu m}f_{UAP}-M\mathbb{E}_{1 \leq j \leq N_0^4}(c_{\mu m, h_j}g_{h_j})\right\|_{L^2} \ll N_0^{-1} −③

が成り立つ。ここで、\mathbb{Z}_N上の\sigma-加法族\mathcal{B}'' \supset \mathcal{B}'

\displaystyle \mathcal{B}'' := \left(\bigvee_{-(k-1)N_0 \leq m \leq (k-1)N_0}T^{\mu m}\mathcal{B}'\right) \vee \left( \bigvee_{0 \leq m  \leq (k-1)N_0, \ 1 \leq j \leq N_0^4}\mathcal{B}_{N_0^{-1}}(c_{\mu m, h_j})\right)

と定義する。このとき、\mathcal{B}''(d-1)-コンパクトな\mathbb{Z}_N上の\sigma-加法族であり、複雑度は高々O_{N_0, X'}(1)=O_{\tau, X, X'}(1)である。理由:

  • c_{\mu m, h_j} \in B(UAP^{d-1})であること
  • \mathcal{B}'(d-1)-コンパクトな\mathbb{Z}_N上の\sigma-加法族で複雑度が高々X'であること
  • §6(その一)で述べた\sigma-加法族のシフトに関する基本性質
  • §6(その二)T^n\mathcal{B}_{\varepsilon}(G)=\mathcal{B}_{\varepsilon}(T^nG)と取っていたこと

に注意すれば、複雑度の定義よりわかる

§6(その二)の命題より、0 \leq m \leq (k-1)N_0, 1 \leq j \leq N_0^4に対して

\displaystyle \left\|c_{\mu m, h_j}-\left.\mathbb{E}(c_{\mu m, h_j}\right|\mathcal{B}'')\right\|_{L^{\infty}} \ll N_0^{-1}

が成り立つ。よって、\left\| \cdot \right\|_{L^2} \leq \left\| \cdot \right\|_{L^{\infty}}L^{\infty}-ノルムの三角不等式、g_{h_j}の有界性などより

\displaystyle \left\|M\mathbb{E}_{1 \leq j \leq N_0^4}(c_{\mu m, h_j}g_{h_j})-M\mathbb{E}_{1 \leq j \leq N_0^4}\left( \left.\mathbb{E}(c_{\mu m, h_j}\right|\mathcal{B}'')g_{h_j}\right) \right\|_{L^2} \ll N_0^{-1}

を得る。③と合わせて、三角不等式を用いると

\displaystyle \left\|T^{\mu m}f_{UAP}-F_{\mu m}\right\|_{L^2} \ll N_0^{-1} −④

が任意の0 \leq m \leq (k-1)N_0で成立する。ここで、n \in \mathbb{Z}_Nに対して

\displaystyle F_n := M\mathbb{E}_{1 \leq j \leq N_0^4}\left(\left.\mathbb{E}(c_{n, h_j}\right|\mathcal{B}'')g_{h_j}\right)

としている。\left.\mathbb{E}(c_{n, h_j}\right|\mathcal{B}'')は有界な\mathcal{B}''-可測関数なので§9の命題(Prop 9.1)を適用することができ、或る整数k_{\ast}=O(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( \mathbb{P}_{\mathbb{Z}_N}\left( \bigcap_{m=1}^{k_{\ast}}E_{\mu \lambda m}\right) \right) −⑤

が成り立つ。ただし、n \in \mathbb{Z}_Nに対して

\displaystyle E_{n} = E_{n}(k, \delta, \mathcal{B}'') =\left\{x \in \mathbb{Z}_N\left|\left.\mathbb{E}(T^{n}f_{U^{\perp}}\right|\mathcal{B}'')(x) \geq \frac{\delta}{2}, \ \left. \mathbb{E}(\left|T^{n}f_{U^{\perp}}-F_{n}\right| \right| \mathcal{B}'')(x) \leq \frac{\delta}{8k}\right\}\right.

であり、N_0N_0\geq k_{\ast}であるようにとっておく。

(その二)では⑤の右辺を上手く評価して帰納法の仮定を適用できるようにする。

*1:Thm 3.3のMは構造定理由来のMで、構造定理ダイコトミーのMとは両立している。

*2:等しいものがあってもよい。また、\muには依存する。

*3:補足:

Chebyshevの不等式 (\Omega, \Sigma, \mu)が測度空間で、A \in \Sigma, \ f\colon A-可測関数、a > 0とすると、
\displaystyle \mu \left(\left\{ x \in A \left|\left|f(x)\right| \geq a \right\}\right. \right) \leq \frac{1}{a^2}\int_{A}\left|f\right|^2d\mu
が成り立つ。
証明. Markovの不等式より、
\displaystyle  \mu \left(\left\{ x \in A \left|\left|f(x)\right| \geq a \right\}\right. \right) = \mu \left(\left\{ x \in A \left|\left|f(x)\right|^2 \geq a^2 \right\}\right. \right) \leq \frac{1}{a^2}\int_{A}\left|f\right|^2d\mu
を得る。 Q.E.D.

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

この記事では、前記事の命題の証明を完成させます。

定義 A\mathbb{Z}_Nの部分集合とし、L^2(A):=\mathrm{Map}(A, \mathbb{C})とする。f, g \in L^2(A)に対して \left\langle f, g\right\rangle_{L^2(A)}:=\mathbb{E}_A(f\overline{g}) とすると、L^2(A)はHilbert空間になる*1f \in L^2(A)に対してL^2(A)-ノルム \left\|f\right\|_{L^2(A)}
\displaystyle \left\|f\right\|_{L^2(A)}:=\sqrt{\mathbb{E}_A(\left|f\right|^2)}
で与えられる。

前記事の第四帰着を更にもう一段階帰着させます。

第五帰着 前記事命題の設定のもと、任意の\delta > 0及びk \in \mathbb{Z}_+に対して或る正整数 k_{\ast}=k_{\ast}(k, \delta, M)が存在し、任意の正整数 \lambdaに対して次が成り立つことを示せば十分である:
前記事①に現れる各アトム A_iに対し、或る1 \leq a, s \leq k_{\ast}/kなるペア(a, s)であって、任意の0 \leq j \leq k-1に対して
\displaystyle \left\|F_{\lambda(a+js)}-F_{\lambda a}\right\|_{L^2(A_i)} \leq \frac{\delta}{8k}
が成り立つようなものが少なくとも一つ存在する。

帰着の確認

第五帰着の主張が成立すると仮定する。\lambda, iを固定し、A_i=Aと略記する。仮定した不等式とCauchy-Schwarzの不等式より、任意の0 \leq j \leq k-1に対して

\displaystyle \mathbb{E}_A\left(\left| F_{\lambda (a+js)}-F_{\lambda a}\right|\right) \leq \frac{\delta}{8k}

が成り立つ。一方、Aの選び方から、任意の0 \leq j \leq k-1に対して

\displaystyle \mathbb{E}_A\left(\left|T^{\lambda(a+js)}f_{U^{\perp}}-F_{\lambda (a+js)}\right|\right) \leq \frac{\delta}{8k}

である。理由: \displaystyle A \subset \bigcap_{m=1}^{k_{\ast}}E_{\lambda m}(k, \delta, \mathcal{B}) 及び 1 \leq a+js \leq k_{\ast} なので、x \in A をとると x \in E_{\lambda (a+js)}(k, \delta, \mathcal{B}) である。よって、この集合の定義とAがアトムであることより、x \in Aを一つ取って

\displaystyle \mathbb{E}_A\left( \left|T^{\lambda(a+js)}f_{U^{\perp}}-F_{\lambda(a+js)}\right|\right)=\left. \mathbb{E}\left(\left|T^{\lambda(a+js)}f_{U^{\perp}}-F_{\lambda(a+js)}\right| \right| \mathcal{B}\right)(x)\leq \frac{\delta}{8k}

が成り立つ j=0の場合の

\displaystyle \mathbb{E}_A\left(\left|T^{\lambda a}f_{U^{\perp}}-F_{\lambda a}\right|\right) \leq \frac{\delta}{8k}

と合わせると、三角不等式によって、任意の0 \leq j \leq k-1に対して

\displaystyle \mathbb{E}_A\left( \left|T^{\lambda(a+js)}f_{U^{\perp}}-T^{\lambda a}f_{U^{\perp}}\right|\right) \leq \frac{3\delta}{8k}

が成り立つことがわかる。この不等式から、任意の0 \leq j \leq k-1に対して

\displaystyle \mathbb{E}_A\left( \mathbf{1}_{\left|T^{\lambda(a+js)}f_{U^{\perp}}-T^{\lambda a}f_{U^{\perp}}\right| > \frac{4}{5}T^{\lambda a}f_{U^{\perp}}} \cdot T^{\lambda a}f_{U^{\perp}} \right) \leq \frac{15\delta}{32 k}

が成り立つ*2x \in Aならば x \in E_{\lambda a}(k, \delta, \mathcal{B}) なので、x \in Aを一つ取って

\displaystyle  \mathbb{E}_A(T^{\lambda a}f_{U^{\perp}})=\left.\mathbb{E}\left(T^{\lambda a}f_{U^{\perp}} \right|\mathcal{B}\right)(x)\geq \frac{\delta}{2}

であることに注意すると、

\begin{align} &\mathbb{E}_A\left( \mathbf{1}_{\left|T^{\lambda(a+js)}f_{U^{\perp}}-T^{\lambda a}f_{U^{\perp}}\right| \leq \frac{4}{5}T^{\lambda a}f_{U^{\perp}}, 0 \leq {}^{\forall}j \leq k-1} \cdot T^{\lambda a}f_{U^{\perp}} \right) \\
&= \mathbb{E}_A(T^{\lambda a}f_{U^{\perp}})-\mathbb{E}_A\left( \mathbf{1}_{\left|T^{\lambda(a+js)}f_{U^{\perp}}-T^{\lambda a}f_{U^{\perp}}\right| > \frac{4}{5}T^{\lambda a}f_{U^{\perp}}, 0 \leq {}^{\exists}j \leq k-1} \cdot T^{\lambda a}f_{U^{\perp}} \right) \\
&\geq  \mathbb{E}_A(T^{\lambda a}f_{U^{\perp}})-\sum_{j=0}^{k-1}\mathbb{E}_A\left( \mathbf{1}_{\left|T^{\lambda(a+js)}f_{U^{\perp}}-T^{\lambda a}f_{U^{\perp}}\right| > \frac{4}{5}T^{\lambda a}f_{U^{\perp}}} \cdot T^{\lambda a}f_{U^{\perp}} \right)\geq \frac{\delta}{2} - \frac{15\delta}{32} \geq \frac{\delta}{32}\end{align}

と評価できる。よって、特性関数はk乗しても変わらないことと、Hölderの不等式と f_{U^{\perp}}の非負性から

\displaystyle \mathbb{E}_A\left( \mathbf{1}_{\left|T^{\lambda(a+js)}f_{U^{\perp}}-T^{\lambda a}f_{U^{\perp}}\right| \leq \frac{4}{5}T^{\lambda a}f_{U^{\perp}}, 0 \leq {}^{\forall}j \leq k-1} \cdot \left(T^{\lambda a}f_{U^{\perp}}\right)^k \right) \geq \left( \frac{\delta}{32}\right)^k

が成り立つことがわかった。ここで、次の不等式が点毎に成り立つことに注意する:

\displaystyle \prod_{j=0}^{k-1}T^{\lambda(a+js)}f_{U^{\perp}} \geq \frac{1}{5^k}\mathbf{1}_{\left|T^{\lambda(a+js)}f_{U^{\perp}}-T^{\lambda a}f_{U^{\perp}}\right| \leq \frac{4}{5}T^{\lambda a}f_{U^{\perp}}, 0 \leq {}^{\forall}j \leq k-1} \cdot  \left(T^{\lambda a}f_{U^{\perp}}\right)^k.

これは、右辺の特性関数の値が0のときは自明に成立し、1のときは任意の0 \leq j \leq k-1に対して

\displaystyle\left|T^{\lambda(a+js)}f_{U^{\perp}}(x)-T^{\lambda a}f_{U^{\perp}}(x)\right| \leq \frac{4}{5}T^{\lambda a}f_{U^{\perp}}(x)

より

\displaystyle T^{\lambda(a+js)}f_{U^{\perp}}(x) \geq \frac{1}{5}T^{\lambda a}f_{U^{\perp}}(x)

であることからわかる。従って、

\displaystyle \mathbb{E}_A\left(\prod_{j=0}^{k-1}T^{\lambda(a+js)}f_{U^{\perp}} \right) \geq \left(\frac{\delta}{160}\right)^k

となって第四帰着の主張が成立する。 確認完了

F_nの定義から目標物は次のように言い換えられます。

第五帰着(言い換え) 前記事命題の設定のもと、任意の\delta > 0及びk \in \mathbb{Z}_+に対して或る正整数 k_{\ast}=k_{\ast}(k, \delta, M)が存在し、任意の正整数 \lambdaに対して次が成り立つことを示せば十分である:
前記事①に現れる各アトム A_iに対し、或る1 \leq a, s \leq k_{\ast}/kなるペア(a, s)であって、任意の0 \leq j \leq k-1に対して
\displaystyle \left\|\mathbb{E}_{h \in H}(c_{\lambda(a+js), h}g_h)-\mathbb{E}_{h \in H}(c_{\lambda a, h}g_h)\right\|_{L^2(A_i)} \leq \frac{\delta}{8Mk}
が成り立つようなものが少なくとも一つ存在する。

帰着は以上で、証明の本質的部分へ入ります。A_i=Aを固定します。

補題 (コンパクト性, Lemma 9.3) これまでの記号設定において、任意のk_{\ast}に対して或る整数
L\ll_{k, M, \delta}11\leq m_1, \dots, m_L \leq k_{\ast}が存在して、
\displaystyle \min_{1 \leq l \leq L}\left\|\mathbb{E}_{h \in H}(c_{\lambda m, h}g_h)-\mathbb{E}_{h \in H}(c_{\lambda m_l, h}g_h)\right\|_{L^2(A)} \leq \frac{\delta}{16Mk}
が任意の1 \leq m \leq k_{\ast}に対して成立する。

証明. 1 \leq m \leq k_{\ast}に対して f_m=\left.\mathbb{E}_{h \in H}(c_{\lambda m, h}g_h)\right|_A \in L^2(A)と略記する。次のアルゴリズムを考える:

  1. 初期化 J:=0
  2. 代入 L^2(A)の部分空間V\displaystyle V:=\begin{cases}\{0\} & (J=0) \\ \langle v_1, \dots, v_J\rangle & (J\geq 1)\end{cases}と定義する。
  3. If 或る1 \leq m \leq k_{\ast}が存在して \displaystyle \mathrm{dist}_{L^2(A)}(f_m, V) \geq \frac{\delta}{64Mk} then 代入 \displaystyle v_{J+1}:=\frac{f_m-\sum_{j=1}^J\langle f_m, v_j\rangle_{L^2(A)} v_j}{\left\|f_m-\sum_{j=1}^J\langle f_m, v_j\rangle_{L^2(A)} v_j\right\|_{L^2(A)}}, \ J:=J+1, 2. へ
  4. else 停止

ここで、\displaystyle \mathrm{dist}_{L^2(A)}(f_m, V) := \inf\{\left\|f_m-v\right\|_{L^2(A)} \mid v \in V\}. 構成の仕方から\{v_j\}は正規直交系をなすが、3. において

\displaystyle \left|\langle f_m, v_{J+1}\rangle_{L^2(A)}\right| \geq \frac{\delta}{64Mk}

を満たしている。理由: 付録で示している等式より

\displaystyle \langle f_m, f_m-\sum_{j=1}^J\langle f_m, v_j\rangle_{L^2(A)} v_j\rangle_{L^2(A)} = \left\|f_m\right\|_{L^2(A)}^2-\sum_{j=1}^J\left|\langle f_m, v_j\rangle_{L^2(A)} \right|^2 = \left\|f_m-\sum_{j=1}^J\langle f_m, v_j\rangle_{L^2(A)}v_j\right\|_{L^2(A)}^2

であり、\displaystyle \sum_{j=1}^J\langle f_m, v_j\rangle_{L^2(A)}v_j \in Vなので

\displaystyle \langle f_m, v_{J+1} \rangle_{L^2(A)} =  \left\|f_m-\sum_{j=1}^J\langle f_m, v_j\rangle_{L^2(A)}v_j\right\|_{L^2(A)} \geq \frac{\delta}{64Mk}

を得る

このアルゴリズムは時間O_{k, M, \delta}(1)で停止する。理由: 構成より各v_jに対して

\displaystyle \left|\langle f_m, v_j\rangle_{L^2(A)}\right| \geq \frac{\delta}{64Mk}

であるようなm=m(j) \in \mathbb{Z}_Nが存在する。内積の公理とc_{\lambda m, h}A上定数であることより

\displaystyle \langle f_m, v_j\rangle_{L^2(A)} = \langle \mathbb{E}_{h \in H}(c_{\lambda m, h}g_h), v_j\rangle_{L^2(A)} = \frac{1}{\#H}\sum_{h \in H}\langle c_{\lambda m, h}g_h, v_j\rangle_{L^2(A)} = \mathbb{E}_{h \in H}(c_{\lambda m, h}\langle g_h, v_j\rangle_{L^2(A)})

であるから、c_{\lambda m, h}の有界性とCauchy-Schwarzの不等式より

\displaystyle \mathbb{E}_{h \in H}\left(\left|\langle g_h, v_j\rangle_{L^2(A)}\right|^2\right) \geq \left|\mathbb{E}_{h \in H}(c_{\lambda m, h}\langle g_h, v_j\rangle_{L^2(A)})\right|^2=\left| \langle f_m, v_j\rangle_{L^2(A)}\right|^2 \geq \left(\frac{\delta}{64Mk}\right)^2

を得る(m(j)はこの時点でなくなる)。j=1, \dots, Jで足し合わせると

\displaystyle \mathbb{E}_{h \in H}\left( \sum_{j=1}^J\left|\langle g_h, v_j\rangle_{L^2(A)}\right|^2\right) \geq \left( \frac{\delta}{64Mk}\right)^2J −①.

h \in Hを固定するとBesselの不等式(付録)とg_hの有界性より

\displaystyle \sum_{j=1}^J\left|\langle g_h, v_j\rangle_{L^2(A)}\right|^2 \leq \left\|g_h\right\|_{L^2(A)}^2 \leq 1

なので、①の左辺は1で上から押さえられる。従って、

\displaystyle J \leq \left( \frac{64Mk}{\delta}\right)^2 = O_{k, M, \delta}(1)

が示された

このアルゴリズムが停止した際のJ次元空間Vを考える。アルゴリズムが停止しているということから、任意の1 \leq m \leq k_{\ast}に対する f_m達はVからL^2(A)-距離にして \delta/64Mkまでのところに住んでいることがわかる。このことから、

f_m達(1 \leq m \leq k_{\ast})の中で、どの二つを取ってもL^2(A)-距離で\frac{\delta}{16Mk}よりも遠く離れているようなものは
高々O_{k, M, \delta, J}(1) = O_{k, M, \delta}(1)個しか選ぶことができない。

ことがわかる。理由:1 \leq m \leq k_{\ast}に対して、最短距離定理(付録)より

\displaystyle \left\|f_m-v_m\right\|_{L^2(A)}=\mathrm{dist}_{L^2(A)}(f_m, V)

なるv_m \in Vが一意的に存在する。このとき、\displaystyle \left\|f_m-v_m\right\|_{L^2(A)} < \frac{\delta}{64Mk}である。

f_m, \ f_{m'}(1 \leq m, m' \leq k_{\ast})が

\displaystyle \left\|f_m-f_{m'}\right\|_{L^2(A)} > \frac{\delta}{16Mk}

を満たすと仮定する。このとき、三角不等式より

\displaystyle \left\|v_m-v_{m'}\right\|_{L^2(A)} \geq \left\|f_m-f_{m'}\right\|_{L^2(A)}-\left\|f_m-v_m\right\|_{L^2(A)}-\left\|f_{m'}-v_{m'}\right\|_{L^2(A)} > \frac{\delta}{32Mk}

が成り立つ。また、c_{\lambda m, h}, g_hが有界であることから f_m\left\|f_m\right\|_{L^2(A)} \leq 1を満たすので、

\displaystyle \left\|v_m\right\|_{L^2(A)} \leq \left\|f_m\right\|_{L^2(A)}+\left\|f_m-v_m\right\|_{L^2(A)} < 1+\frac{\delta}{64Mk}

である(v_{m'}についても同様)。従って、

\displaystyle \left\{ v \in V \left| \left\|v\right\|_{L^2(A)} < 1+\frac{\delta}{64Mk} \right\}\right.

の元達であって、どの二つを取ってもL^2(A)-距離で\delta/32Mkよりも遠く離れているようなものは高々O_{k, M, \delta, J}(1)個しか選ぶことができない*3ことから主張が従う

よって、f_m(1 \leq m \leq k_{\ast})の中から適当に f_{m_1}, \dots, f_{m_L}を選んで、これらの中からどの二つを取ってもL^2(A)-距離で\frac{\delta}{16Mk}よりも遠く離れているが、これら以外の f_mについては必ず f_{m_1}, \dots, f_{m_L}のいずれかと\frac{\delta}{16Mk}以下の距離になるようにすれば(k_{\ast}は有限なので選べる*4 )、直前に確認した事実からL=O_{k, M, \delta}(1)である。この f_{m_1}, \dots, f_{m_L}に対して補題の主張が成立している。 Q.E.D.

前記事命題の証明

k_{\ast}=k_{\ast}(k, \delta, M):=k\times N_{\mathrm{vdW}}(k, O_{k, M, \delta}(1))とする。ここで、O_{k, M, \delta}(1)は補題のLに対するバウンドで、N_{\mathrm{vdW}}(k, m)van der Waerdenの定理によって存在する整数。このk_{\ast}に対して補題によって存在するL \ll_{k, M, \delta} 1, \ 1 \leq m_1, \dots, m_L \leq k_{\ast}をとって、色塗り写像c\colon \{1, \dots, k_{\ast}\} \to \{1, \dots, L\}

\displaystyle c(m) := \min\left\{1 \leq l \leq L \left| \left\|\mathbb{E}_{h \in H}(c_{\lambda m, h}g_h)-\mathbb{E}_{h \in H}(c_{\lambda m_l, h}g_h)\right\|_{L^2(A)} \leq \frac{\delta}{16MK}\right\}\right.

と定義する。cがwell-definedであることは補題の主張からわかる。よって、van der Waerdenの定理により整数 1 \leq a, s \leq k_{\ast}/kが存在して、長さkの等差数列

\displaystyle a, \ a+s, \ \dots, \ a+(k-1)s

は同じ色で塗られている。すなわち、或る1 \leq l \leq Lが存在して、任意の0 \leq j \leq k-1に対して

\displaystyle \left\|\mathbb{E}_{h \in H}(c_{\lambda (a+js), h}g_h)-\mathbb{E}_{h \in H}(c_{\lambda m_l, h}g_h)\right\|_{L^2(A)} \leq \frac{\delta}{16MK}

が成り立つ。従って、任意の0 \leq j \leq k-1に対して

\begin{align}&\left\|\mathbb{E}_{h \in H}(c_{\lambda (a+js), h}g_h)-\mathbb{E}_{h \in H}(c_{\lambda a, h}g_h)\right\|_{L^2(A)} \\
&\leq  \left\|\mathbb{E}_{h \in H}(c_{\lambda (a+js), h}g_h)-\mathbb{E}_{h \in H}(c_{\lambda m_l, h}g_h)\right\|_{L^2(A)}+\left\|\mathbb{E}_{h \in H}(c_{\lambda a, h}g_h)-\mathbb{E}_{h \in H}(c_{\lambda m_l, h}g_h)\right\|_{L^2(A)} \leq \frac{\delta}{8Mk}\end{align}

と評価でき、第五帰着(言い換え)の主張が証明された。以上で、前記事の命題の証明が完了する。 Q.E.D.

付録 Besselの不等式

命題 (\mathcal{H}, \langle \cdot, \cdot \rangle)をHilbert空間とし、\{x_i\}_{i=1}^nを正規直交系とする。このとき、任意のx \in \mathcal{H}に対して
\displaystyle \left\|x-\sum_{i=1}^n\langle x, x_i\rangle x_i\right\|^2=\left\|x\right\|^2-\sum_{i=1}^n\left|\langle x, x_i\rangle \right|^2
が成り立つ。よって、特にBesselの不等式
\displaystyle \sum_{i=1}^n\left|\langle x, x_i\rangle\right|^2 \leq \left\|x\right\|^2
が成立する*5

証明. 内積の公理に従って計算をすると

\displaystyle \left\|x-\sum_{i=1}^n\langle x, x_i\rangle x_i\right\|^2 = \left\|x\right\|^2-\sum_{i=1}^n\overline{\langle x, x_i\rangle}\langle x, x_i\rangle - \sum_{i=1}^n\langle x, x_i\rangle \langle x_i, x\rangle + \sum_{i, j=1}^n\langle x, x_i\rangle \overline{\langle x, x_j\rangle}\langle x_i, x_j \rangle

と展開される。三つの和について最初の二つは明らかに \displaystyle \sum_{i=1}^n\left|\langle x, x_i\rangle \right|^2であるが、最後の和についても\{x_i\}_{i=1}^nが正規直交系であることに注意すれば同じく \displaystyle \sum_{i=1}^n\left|\langle x, x_i\rangle \right|^2であることがわかる。 Q.E.D.

付録 最短距離定理

命題 (\mathcal{H}, \langle \cdot, \cdot \rangle)をHilbert空間とし、V\mathcal{H}の閉凸部分集合とする。このとき、任意のx \in \mathcal{H}に対して一意的にv_0 \in Vが存在して
\displaystyle \left\|x-v_0\right\| = \mathrm{dist}(x, V) = \inf\left\{\left\|x-v\right\| \left| v \in V\right\}\right.
が成り立つ。

証明. d=\mathrm{dist}(x, V)とする。下限の定義よりVの列\{v_n\}_{n=1}^{\infty}であって

\displaystyle \lim_{n \to \infty}\left\|x-v_n\right\|=d

が成り立つようなものが存在する。中線定理より

\begin{align} \left\|v_n-v_m\right\|^2 &= \left\|(x-v_n)-(x-v_m)\right\|^2+\left\|(x-v_n)+(x-v_m)\right\|^2-\left\|(x-v_n)+(x-v_m)\right\|^2 \\
&= 2\left\|x-v_n\right\|^2+2\left\|x-v_m\right\|^2-\left\|(x-v_n)+(x-v_m)\right\|^2\end{align}

と計算できるが、Vの凸性より

\displaystyle \left\|(x-v_n)+(x-v_m)\right\|^2 = 4\left\|x-\frac{v_n+v_m}{2}\right\|^2 \geq 4d^2

なので

\displaystyle \left\|v_n-v_m\right\|^2 \leq 2\left\|x-v_n\right\|^2+2\left\|x-v_m\right\|^2-4d^2

と評価できる。よって、v_n, v_mの取り方から\{v_n\}はCauchy列をなすことがわかる。\mathcal{H}がHilbert空間でVは閉なので、

\displaystyle v_0 := \lim_{n \to \infty}v_n \in V

が存在する。このとき、

\displaystyle \left\|x-v_0\right\| = \lim_{n \to \infty}\left\|x-v_n\right\|=d

が成り立つ。一意性を示すために d=\left\|x-v\right\|なるv \in Vをとる。先ほどと同じ計算によって

\displaystyle 0 \leq \left\|v-v_0\right\|^2\leq 2\left\|x-v\right\|^2+2\left\|v-v_0\right\|^2-4d^2=0

なので、v=v_0が従う。 Q.E.D.

本文ではVが有限次元部分空間の場合に最短距離定理を適用します。

補題 (\mathcal{H}, \langle \cdot, \cdot \rangle)をHilbert空間とし、V\mathcal{H}の有限次元部分空間とする。このとき、Vは閉かつ凸である。

証明. 部分空間が凸であることは明らか。閉であることは完備性から出る(§5(その一)の付録を参照)。 Q.E.D.

*1:Hilbert空間になることはL^2(\mathbb{Z}_N)=\mathrm{Map}(\mathbb{Z}_N, \mathbb{C})の場合と同様に確かめられる。

*2:これはMarkovの不等式の証明と丸っきり同様にすればよい。

*3:Aに依存しないことは、Vの正規直交基底を取っているため、v \in Vに対して\left\|v\right\|_{\infty}\leq \left\|v\right\|_{L^2(A)} \leq J\left\|v\right\|_{\infty}が成り立つことから分かる(v=\sum_{j=1}^J\alpha_jv_jに対して、\left\|v\right\|_{\infty}:=\max\{\left|\alpha_j\right|\})。

*4:f_{m_1}, \dots, f_{m_j}が選ばれているときに、そのいずれとも\delta/16Mkより遠く離れているf_mがあれば、それ(その中で一番近いもの)をf_{m_{j+1}}とする。なければ停止する。グリーディ法。

*5:Hilbert空間であることが効いてくるのはn \to \inftyとした場合ですが、この記事では有限版Besselの不等式で十分です。

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

§9 Compactness on atoms, and an application of van der Waerden's theorem を二回に分けて読んでいきます。残すところは構造化回帰定理(Thm 3.3)のみですが、これは§9と§10の二節を使って証明されている最も難しい部分となります。この記事ではKeyとなる命題を紹介し、その命題からThm 3.3のd=1の場合が出ることを確認します。そして、命題の証明は幾つかの帰着をしながら実行されますが、第四帰着までを扱います。

命題 (条件付き一様概周期関数に対する回帰性, Proposition 9.1)
(データ)
\mathcal{B}\mathbb{Z}_N上の\sigma-加法族、Mを正の実数、Hを空でない有限集合とする。各 n \in \mathbb{Z}_N, \ h \in H 毎にc_{n, h}を有界\mathcal{B}-可測関数とし、各h \in Hに対しg_hを有界関数とする。これらの関数を用いて、各n \in \mathbb{Z}_N毎に関数F_n
F_n:=M\mathbb{E}_{h \in H}(c_{n, h}g_h)

と定義する。f_{U^{\perp}}は非負値有界関数とする。
(定義) 実数\delta > 0, 正整数 k \in \mathbb{Z}_+, n \in \mathbb{Z}_Nに対して集合E_n(k, \delta, \mathcal{B})

\displaystyle E_n(k, \delta, \mathcal{B}):=\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}}-F_n\right| \right| \mathcal{B})(x) \leq \frac{\delta}{8k}\right\}\right.

と定義する。
(主張) 以上の設定のもと、任意の\delta > 0及びk \in \mathbb{Z}_+に対し、或る正整数 k_{\ast}=k_{\ast}(k, \delta, M)が存在して

\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_{k, \delta, M}\mathbb{E}_{1 \leq \lambda \leq \frac{N_0}{k_{\ast}}}\left(\mathbb{P}_{\mathbb{Z}_N}\left( \bigcap_{m=1}^{k_{\ast}}E_{\mu \lambda m}(k, \delta, \mathcal{B})\right) \right)

が任意の\mu \in \mathbb{Z}_Nと整数 N_0 \geq k_{\ast}に対して成立する(r, \lambdaは整数を動く)。

構造化回帰定理のd=1の場合の証明

(再掲) 一様概周期関数の回帰性 (Theorem 3.3) d \geq 0, k\geq 1を整数とする。非負値有界関数 f_{U^{\perp}}, f_{UAP}は或る 0 < \delta \leq 1, M > 0に対して
1. \displaystyle \left\| f_{U^{\perp}}-f_{UAP} \right\|_{L^2} \leq \frac{\delta^2}{1024k},\quad 2. \displaystyle \int_{\mathbb{Z}_N}f_{U^{\perp}} \geq \delta,\quad 3. \left\|f_{UAP}\right\|_{UAP^d} < M
を満たすと仮定する。このとき、任意の\mu \in \mathbb{Z}_N及び正整数N_1に対して
\displaystyle \mathbb{E}_{0 \leq r \leq N_1}\left( \int_{\mathbb{Z}_N}\prod_{j=0}^{k-1}T^{\mu jr}f_{U^{\perp}}\right) \gg_{d, k, \delta, M} 1
が成り立つ。

命題を仮定した上でのd=1の場合の証明

Thm 3.3のd=1の場合のf_{U^{\perp}}, f_{UAP}, k, M, \deltaを取る。\left\|f_{UAP}\right\|_{UAP^1} < Mなので、一様概周期関数の定義によって、空でない有限集合Hn \in \mathbb{Z}_N, \ h \in H毎に定まる絶対値1以下の複素数c_{n, h}, h \in H毎に定まる有界関数 g_hが存在して、任意のn \in \mathbb{Z}_Nに対して

\displaystyle T^nf_{UAP} = F_n = M\mathbb{E}_{h \in H}(c_{n, h}g_h)

と表示できる。\mathcal{B}=\{\emptyset, \mathbb{Z}_N\}とすれば \mathcal{B}-可測関数 = 定数関数となるので、冒頭の命題が適用可能な状況となった。よって、命題よりk_{\ast}が存在し、任意の\mu \in \mathbb{Z}_Nと整数N_1 \geq k_{\ast}に対して、

\displaystyle \mathbb{E}_{1 \leq r \leq N_1}\left(\int_{\mathbb{Z}_N}\prod_{j=0}^{k-1}T^{\mu jr}f_{U^{\perp}}\right) \gg_{k, \delta, M}\mathbb{E}_{1 \leq \lambda \leq \frac{N_1}{k_{\ast}}}\left(\mathbb{P}_{\mathbb{Z}_N}\left( \bigcap_{m=1}^{k_{\ast}}E_{\mu \lambda m}(k, \delta, \mathcal{B})\right) \right)

が成立する。実は、考察中の各\mu, \lambda, mに対して E_{\mu \lambda m}(k, \delta, \mathcal{B})=\mathbb{Z}_N が確認できる。そのためには、

\displaystyle \int_{\mathbb{Z}_N}T^{\mu \lambda m}f_{U^{\perp}} \geq \frac{\delta}{2}, \quad \int_{\mathbb{Z}_N}\left|T^{\mu \lambda m}f_{U^{\perp}}-F_{\mu \lambda m}\right| \leq \frac{\delta}{8k}

が成り立つことを確認すればよい。一つ目は \displaystyle \int_{\mathbb{Z}_N}f_{U^{\perp}} \geq \delta であることと積分のシフト不変性から従う。二つ目は積分のシフト不変性とCauchy-Schwarzの不等式より

\begin{align} \int_{\mathbb{Z}_N}\left|T^{\mu \lambda m}f_{U^{\perp}}-F_{\mu \lambda m}\right| &= \int_{\mathbb{Z}_N}T^{\mu \lambda m}\left|f_{U^{\perp}}-f_{UAP}\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} \leq \frac{\delta}{8k}\end{align}

と確認できる。従って、今のケースでは

\displaystyle \mathbb{E}_{1 \leq \lambda \leq \frac{N_1}{k_{\ast}}}\left(\mathbb{P}_{\mathbb{Z}_N}\left( \bigcap_{m=1}^{k_{\ast}}E_{\mu \lambda m}(k, \delta, \mathcal{B})\right) \right)=1

である。f_{U^{\perp}}は非負値なので、

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

であり、N_1 \geq k_{\ast}の場合は所望の不等式が得られたことになる。N_1 < k_{\ast}の場合は f_{U^{\perp}}が非負値なので

\displaystyle k_{\ast}\mathbb{E}_{0 \leq r \leq N_1}\left(\int_{\mathbb{Z}_N}\prod_{j=0}^{k-1}T^{\mu jr}f_{U^{\perp}}\right) \geq \int_{\mathbb{Z}_N}f_{U^{\perp}}^k \geq \left(\int_{\mathbb{Z}_N}f_{U^{\perp}}\right)^k \geq \delta^k

と評価でき(Hölderの不等式を用いた)、k_{\ast}k, \delta, Mで決まるので

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

を得る。 Q.E.D.

なお、非負値有界関数 f_{UAP}\left\|f_{UAP}\right\|_{UAP^0} < M を満たせば

\displaystyle \left\|f_{UAP}\right\|_{UAP^1} \leq \left\|f_{UAP}\right\|_{UAP^0} < M

なので、d=1の場合からd=0の場合も従う。

命題の証明

それでは命題の証明を始めます。この記事では四段階帰着させます。

第一帰着 命題の設定のもと、任意の\delta > 0及びk \in \mathbb{Z}_+に対して或る正整数 k_{\ast}=k_{\ast}(k, \delta, M)が存在し、任意の\mu \in \mathbb{Z}_Nと整数 N_0 \geq k_{\ast}に対して
\displaystyle \mathbb{E}_{1 \leq a, s \leq \frac{k_{\ast}}{k}}\left( \int_{\mathbb{Z}_N}\prod_{j=0}^{k-1}T^{\mu \lambda (a+js)}f_{U^{\perp}}\right) \gg_{\delta, k, k_{\ast}} \mathbb{P}_{\mathbb{Z}_N}\left(\bigcap_{m=1}^{k_{\ast}}E_{\mu \lambda m}(k, \delta, \mathcal{B})\right)
が各 1 \leq \lambda \leq N_0/k_{\ast} について成り立つことを示せばよい。ここで、a, s, \lambdaは整数。

帰着の確認

第一帰着の主張が証明されたと仮定する。このとき、\lambdaについて平均を取れば

\displaystyle \mathbb{E}_{1\leq \lambda \leq \frac{N_0}{k_{\ast}}; 1 \leq a, s \leq \frac{k_{\ast}}{k}}\left( \int_{\mathbb{Z}_N}\prod_{j=0}^{k-1}T^{\mu \lambda (a+js)}f_{U^{\perp}}\right)\gg_{\delta, k, k_{\ast}}\mathbb{E}_{1 \leq \lambda \leq \frac{N_0}{k_{\ast}}}\left( \mathbb{P}_{\mathbb{Z}_N}\left(\bigcap_{m=1}^{k_{\ast}}E_{\mu \lambda m}(k, \delta, \mathcal{B})\right) \right)

が得られる。シフト作用素の性質により

\displaystyle \prod_{j=0}^{k-1}T^{\mu \lambda(a+js)}f_{U^{\perp}} = \prod_{j=0}^{k-1}T^{\mu \lambda a}\left( T^{\mu \lambda js}f_{U^{\perp}}\right) = T^{\mu \lambda a}\Biggl(\prod_{j=0}^{k-1}T^{\mu \lambda js}f_{U^{\perp}}\Biggr)

と変形できるので、積分のシフト不変性から

\displaystyle \mathbb{E}_{1\leq \lambda \leq \frac{N_0}{k_{\ast}}; 1 \leq a, s \leq \frac{k_{\ast}}{k}}\left( \int_{\mathbb{Z}_N}\prod_{j=0}^{k-1}T^{\mu \lambda js}f_{U^{\perp}}\right) \gg_{\delta, k, k_{\ast}}\mathbb{E}_{1 \leq \lambda \leq \frac{N_0}{k_{\ast}}}\left( \mathbb{P}_{\mathbb{Z}_N}\left(\bigcap_{m=1}^{k_{\ast}}E_{\mu \lambda m}(k, \delta, \mathcal{B})\right) \right)

を得る。左辺の期待値の中身はaに依らないので、

\displaystyle \mathbb{E}_{1\leq \lambda \leq \frac{N_0}{k_{\ast}}; 1 \leq s \leq \frac{k_{\ast}}{k}}\left( \int_{\mathbb{Z}_N}\prod_{j=0}^{k-1}T^{\mu \lambda js}f_{U^{\perp}}\right) \gg_{\delta, k, k_{\ast}}\mathbb{E}_{1 \leq \lambda \leq \frac{N_0}{k_{\ast}}}\left( \mathbb{P}_{\mathbb{Z}_N}\left(\bigcap_{m=1}^{k_{\ast}}E_{\mu \lambda m}(k, \delta, \mathcal{B})\right) \right)

と書き直せる。ここで、1 \leq r \leq N_0/k なる整数r

\displaystyle r=\lambda s, \quad 1 \leq \lambda \leq \frac{N_0}{k_{\ast}}, \ 1 \leq s \leq \frac{k_{\ast}}{k}

と表示する場合の数は高々\displaystyle \left[ \frac{k_{\ast}}{k}\right] = O_{k, k_{\ast}}(1) なので、f_{U^{\perp}}の非負性より

\begin{align}&\left[\frac{N_0}{k_{\ast}}\right] \times \left[\frac{k_{\ast}}{k}\right]\mathbb{E}_{1 \leq \lambda \leq \frac{N_0}{k_{\ast}}; 1 \leq s \leq \frac{k_{\ast}}{k}}\left(\int_{\mathbb{Z}_N}\prod_{j=0}^{k-1}T^{\mu \lambda js}f_{U^{\perp}} \right)
\\ &\leq O_{k, k_{\ast}}(1)\left[ \frac{N_0}{k}\right]\mathbb{E}_{1 \leq r \leq \frac{N_0}{k}}\left(\int_{\mathbb{Z}_N}\prod_{j=0}^{k-1}T^{\mu jr}f_{U^{\perp}}\right) \leq O_{k, k_{\ast}}(1)N_0\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) \end{align}

と評価できる。すなわち、

\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_{k, k_{\ast}} \mathbb{E}_{1\leq \lambda \leq \frac{N_0}{k_{\ast}}; 1 \leq s \leq \frac{k_{\ast}}{k}}\left( \int_{\mathbb{Z}_N}\prod_{j=0}^{k-1}T^{\mu \lambda js}f_{U^{\perp}}\right)

がわかったので、

\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_{\delta, k, k_{\ast}}\mathbb{E}_{1 \leq \lambda \leq \frac{N_0}{k_{\ast}}}\left( \mathbb{P}_{\mathbb{Z}_N}\left(\bigcap_{m=1}^{k_{\ast}}E_{\mu \lambda m}(k, \delta, \mathcal{B})\right) \right)

が得られた。k_{\ast}は最終的にk, \delta, Mから決まるので命題が従う。 確認完了

第二帰着 命題の設定のもと、任意の\delta > 0及びk \in \mathbb{Z}_+に対して或る正整数 k_{\ast}=k_{\ast}(k, \delta, M)が存在し、任意の正整数 \lambdaに対して
\displaystyle \mathbb{E}_{1 \leq a, s \leq \frac{k_{\ast}}{k}}\left( \int_{\mathbb{Z}_N}\prod_{j=0}^{k-1}T^{\lambda (a+js)}f_{U^{\perp}}\right) \gg_{\delta, k, k_{\ast}} \mathbb{P}_{\mathbb{Z}_N}\left(\bigcap_{m=1}^{k_{\ast}}E_{\lambda m}(k, \delta, \mathcal{B})\right)
が成り立つことを示せばよい。ここで、a, s, \lambdaは整数。

帰着の確認

第二帰着の主張が証明されれば、\lambdaには制限がないので、\lambda \mapsto \mu \lambdaとすることにより第一帰着の主張が従う*1確認完了

補題 命題の主張中で定義されている集合E_{n}(k, \delta, \mathcal{B})\mathcal{B}の元である(\mathcal{B}-可測集合)。

証明. x \in E_{n}(k, \delta, \mathcal{B})をとると、\mathcal{B}-可測関数はアトム上定数なので、定義より

\mathcal{B}(x) \subset E_{n}(k, \delta, \mathcal{B})

である(\mathcal{B}(x)xを含むような\mathcal{B}のアトム)。このことから、E_{n}(k, \delta, \mathcal{B})は幾つかのアトムの和集合として書けることがわかる。 Q.E.D.

よって、\displaystyle \bigcap_{m=1}^{k_{\ast}}E_{\lambda m}(k, \delta, \mathcal{B})\mathcal{B}-可測集合であり、

\displaystyle \bigcap_{m=1}^{k_{\ast}}E_{\lambda m}(k, \delta, \mathcal{B}) = \bigsqcup_{i=1}^KA_i –①

\mathcal{B}のアトムの和集合として書ける(K及びA_i\delta, k, k_{\ast}, \lambda, \mathcal{B}に依存して定まる)。

第三帰着 命題の設定のもと、任意の\delta > 0及びk \in \mathbb{Z}_+に対して或る正整数 k_{\ast}=k_{\ast}(k, \delta, M)が存在し、任意の正整数 \lambdaに対して次が成り立つことを示せば十分である:
①に現れる任意のアトム A_iに対し、
\displaystyle \mathbb{E}_{1 \leq a, s \leq \frac{k_{\ast}}{k}}\left( \mathbb{E}_{A_i}\left( \prod_{j=0}^{k-1}T^{\lambda(a+js)}f_{U^{\perp}}\right)\right) \gg_{\delta, k, k_{\ast}} 1
が成立する。

帰着の確認

第三帰着の主張が各A_iに対して示されたとする。このとき、各不等式の両辺に \mathbb{P}_{\mathbb{Z}_N}(A_i) を掛けてi=1, \dots, Kで足し合わせる。その結果、右辺は

\displaystyle \sum_{i=1}^K\mathbb{P}_{\mathbb{Z}_N}(A_i) = \mathbb{P}_{\mathbb{Z}_N}\left(\bigcap_{m=1}^{k_{\ast}}E_{\lambda m}(k, \delta, \mathcal{B})\right)

であり、a, sを固定するとき

\displaystyle \sum_{i=1}^K\mathbb{P}_{\mathbb{Z}_N}(A_i)\mathbb{E}_{A_i}\left(\prod_{j=0}^{k-1}T^{\lambda(a+js)}f_{U^{\perp}}\right) = \int_{\mathbb{Z}_N }\prod_{j=0}^{k-1}T^{\lambda (a+js)}f_{U^{\perp}}

なので、和の取り換えによって左辺は

\displaystyle \sum_{i=1}^K\mathbb{P}_{\mathbb{Z}_N}(A_i)\mathbb{E}_{1 \leq a, s \leq \frac{k_{\ast}}{k}}\left( \mathbb{E}_A\left( \prod_{j=0}^{k-1}T^{\lambda(a+js)}f_{U^{\perp}}\right)\right) = \mathbb{E}_{1 \leq a, s \leq \frac{k_{\ast}}{k}}\left( \int_{\mathbb{Z}_N}\prod_{j=0}^{k-1}T^{\lambda (a+js)}f_{U^{\perp}}\right)

となる。すなわち、第二帰着の主張が示される。 確認完了

第四帰着 命題の設定のもと、任意の\delta > 0及びk \in \mathbb{Z}_+に対して或る正整数 k_{\ast}=k_{\ast}(k, \delta, M)が存在し、任意の正整数 \lambdaに対して次が成り立つことを示せば十分である:
①に現れる各アトム A_iに対し、或る1 \leq a, s \leq k_{\ast}/kなるペア(a, s)であって
\displaystyle \mathbb{E}_{A_i}\left( \prod_{j=0}^{k-1}T^{\lambda(a+js)}f_{U^{\perp}}\right) \gg_{\delta, k}1
が成り立つようなものが少なくとも一つ存在する。

帰着の確認

第四帰着の主張が示されたと仮定する。\lambda, \ iを固定して、仮定によって存在する特別なペアを(b, t)とする。1 \leq a, s \leq k_{\ast}/kなるペア(a, s)の個数は高々O_{k, k_{\ast}}(1)なので、f_{U^{\perp}}の非負性より

\displaystyle O_{k, k_{\ast}}(1) \mathbb{E}_{1 \leq a, s \leq \frac{k_{\ast}}{k}}\left( \mathbb{E}_{A_i}\left( \prod_{j=0}^{k-1}T^{\lambda(a+js)}f_{U^{\perp}}\right)\right) \geq \mathbb{E}_{A_i}\left( \prod_{j=0}^{k-1}T^{\lambda(b+jt)}f_{U^{\perp}}\right) \gg_{\delta, k}1

であり、

\displaystyle \mathbb{E}_{1 \leq a, s \leq \frac{k_{\ast}}{k}}\left( \mathbb{E}_{A_i}\left( \prod_{j=0}^{k-1}T^{\lambda(a+js)}f_{U^{\perp}}\right)\right) \gg_{\delta, k, k_{\ast}} 1

となって、第三帰着の主張が示される。 確認完了

*1:ここは\mathrm{pr}_N\colon \mathbb{Z} \to \mathbb{Z}_Nの省略が散見されます。