タオのセメレディ論文の§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)の記号における定数についても同様である。

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

を満たすと仮定する。 $\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の補題における $m$ は $m=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$ であることから、空でない有限集合 $H$ 、 $n \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_0$ は $N_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.

2017-09-21

タオのセメレディ論文の§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空間になる*1。 $f \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}$

が成り立つ*2。 $x \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}1$ と $1\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)$ と略記する。次のアルゴリズムを考える：

初期化 $J:=0$
代入 $L^2(A)$ の部分空間 $V$ を $\displaystyle V:=\begin{cases}\{0\} & (J=0) \\ \langle v_1, \dots, v_J\rangle & (J\geq 1)\end{cases}$ と定義する。
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. へ
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$

なので

と評価できる。よって、 $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$ をとる。先ほどと同じ計算によって

なので、 $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の不等式で十分です。

2017-09-21

タオのセメレディ論文の§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$ に対して

を満たすと仮定する。このとき、任意の $\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$ なので、一様概周期関数の定義によって、空でない有限集合 $H$ と $n \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$ の省略が散見されます。

INTEGERS

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

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

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

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

補題の証明

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

帰着の確認

前記事命題の証明

付録 Besselの不等式

付録最短距離定理

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

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

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

命題の証明

帰着の確認

帰着の確認

帰着の確認

帰着の確認

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

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

補題の証明

帰着の確認

前記事命題の証明

付録 Besselの不等式

付録 最短距離定理

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

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

命題の証明

帰着の確認

帰着の確認

帰着の確認

帰着の確認

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

付録最短距離定理

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

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