インテジャーズ

INTEGERS

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

タオのセメレディ論文の§8を読む

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

§8 Proof of the structure theorem では前節のエネルギー増加法を用いて構造定理(Thm 3.5)を証明します。

命題 (構造定理ダイコトミー, Lemma 8.1) k \geq 3を整数とし、非負値有界関数 f\colon \mathbb{Z}_N \to \mathbb{R}^+は或る0 < \delta \leq 1に対して条件
\displaystyle \int_{\mathbb{Z}_N}f \geq \delta
を満たすと仮定する。F \colon \mathbb{R}^+ \to \mathbb{R}^+を任意の関数とする。また、X, \ X' \geq 0は整数で、\mathcal{B} (resp. \mathcal{B}')をそれぞれ複雑度がX (resp. X')以下であるような(k-2)-コンパクトな\mathbb{Z}_N上の\sigma-加法族であって、\mathcal{B} \subset \mathcal{B}' 及び エネルギーギャップ条件
\displaystyle \mathcal{E}_{f}(\mathcal{B}')-\mathcal{E}_f(\mathcal{B}) \leq \left(\frac{\delta^2}{2048k}\right)^2
を満たすようなものとする。このとき、次の少なくとも一方を満たす：

(成功): 或る M=O_{k, \delta, X}(1), 有界関数 f_U \colon \mathbb{Z}_N \to \mathbb{C}, 非負値有界関数 f_{U^{\perp}}, \ f_{UAP} \colon \mathbb{Z}_N \to \mathbb{R}^+が存在して

\begin{align}&\cdot \ f=f_U+f_{U^{\perp}}, \quad \cdot \ \left\| f_{U^{\perp}}-f_{UAP} \right\|_{L^2} \leq  \frac{\delta^2}{1024k},\quad \cdot \ \int_{\mathbb{Z}_N}f_{U^{\perp}} \geq \delta,\\ &\cdot \ \left\|f_{UAP}\right\|_{UAP^{k-2}} < M, \quad \cdot \ \left\|f_U\right\|_{U^{k-1}} \leq \frac{1}{F(M)}\end{align}
が成り立つ。

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

\displaystyle \mathcal{E}_f(\mathcal{B}'')-\mathcal{E}_f(\mathcal{B}') \gg_{k, \delta, X, F}1
が生じる。

証明. fが非負値有界関数であることから、\left.\mathbb{E}(f\right|\mathcal{B})も非負値有界関数であることに注意する。\mathcal{B}は複雑度がX以下の(k-2)-コンパクトな\mathbb{Z}_N上の\sigma-加法族なので、非負値有界\mathcal{B}-可測関数 \left.\mathbb{E}(f\right|\mathcal{B}) に§6(その三)の命題を適用することによって、非負値有界関数 f_{UAP} \in UAP^{k-2}と或る M=O_{k, \delta, X}(1)が存在して、

\displaystyle \left\|\left.\mathbb{E}(f\right|\mathcal{B})-f_{UAP}\right\|_{L^2} \leq \frac{\delta^2}{2048k}

及び

\displaystyle \left\|f_{UAP}\right\|_{UAP^{k-2}} < M

が成り立つようにできることがわかる(一つとって固定する)。ここで、f_{U^{\perp}}:= \left.\mathbb{E}(f\right|\mathcal{B}'), \ f_U:=f-\left.\mathbb{E}(f\right|\mathcal{B}') と定義する。このように定義すると f=f_U+f_{U^{\perp}} が成り立っており、f_{U^{\perp}}はやはり非負値有界関数で、fと f_{U^{\perp}}の非負値有界性から f_{U}の有界性が従う(非負値とは限らない)。

エネルギーギャップ公式より

\displaystyle \left\|\left.\mathbb{E}(f\right|\mathcal{B}')-\left.\mathbb{E}(f\right|\mathcal{B})\right\|_{L^2}^2=\mathcal{E}_f(\mathcal{B}')-\mathcal{E}_f(\mathcal{B})\leq \left(\frac{\delta^2}{2048k}\right)^2

が成り立つので、L^2-ノルムの三角不等式により

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

と評価できる。また、条件付き期待値作用素をとっても積分値は変わらなかったので、

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

である。あとは、\left\|f_U\right\|_{U^{k-1}} \leq 1/F(M)であればダイコトミーの(成功)が成立することになる。よって、

\displaystyle \left\|f_U\right\|_{U^{k-1}} > \frac{1}{F(M)}

と仮定して(エネルギー増加)を示す。このように仮定するとき、§5(その二)の命題２より

\displaystyle \left|\left\langle f_U, G\right\rangle \right| \geq \left(\frac{1}{F(M)}\right)^{2^{k-1}}

を満たすような有界関数 G \in B(UAP^{k-2})が存在する( f_Uが有界であることに注意)。すなわち、

\displaystyle \left|\left\langle f_U, G\right\rangle \right| \gg_{k, \delta, X, F} 1

である。このGと後でk, \delta, X, Fに依存して選択する\varepsilon > 0を用いて

\displaystyle \mathcal{B}'':= \mathcal{B}'\vee \mathcal{B}_{\varepsilon}(G)

と\mathcal{B}''を定義する。これは\mathcal{B}'を含む(k-2)-コンパクトな\mathbb{Z}_N上の\sigma-加法族なので、後は複雑度とエネルギーを計算すればよい。

f_UとGを

\begin{align}f_U&=\left(f-\left.\mathbb{E}(f\right|\mathcal{B}'')\right)+\left(\left.\mathbb{E}(f\right|\mathcal{B}'')-\left.\mathbb{E}(f\right|\mathcal{B}')\right) \\ G&= \left( G-\left.\mathbb{E}(G\right|\mathcal{B}'')\right)+\left(\left.\mathbb{E}(G\right|\mathcal{B}'')-\left.\mathbb{E}(G\right|\mathcal{B}')\right)+\left.\mathbb{E}(G\right|\mathcal{B}')\end{align}

と分解すると、ともに第一項は\mathcal{B}''と直交し(§6(その一)補題２)、従って\mathcal{B}'とも直交する(§6(その一)補題３の証明中の式より)。第二項は\mathcal{B}''-可測かつ\mathcal{B}'と直交(§6(その一)補題３)、Gの第三項は\mathcal{B}'-可測である。

これより、

\displaystyle \left\langle f_U, G\right\rangle = \left\langle f-\left.\mathbb{E}(f\right|\mathcal{B}''), G-\left.\mathbb{E}(G\right|\mathcal{B}'')\right\rangle+\left\langle \left.\mathbb{E}(f\right|\mathcal{B}'')-\left.\mathbb{E}(f\right|\mathcal{B}'), \left.\mathbb{E}(G\right|\mathcal{B}'')-\left.\mathbb{E}(G\right|\mathcal{B}')\right\rangle

を得る*1。

§6(その二)の命題より

\displaystyle \left\|G-\left.\mathbb{E}(G\right|\mathcal{B}'')\right\|_{L^{\infty}} \ll \varepsilon

である。f-\left.\mathbb{E}(f\right|\mathcal{B}'')が有界であることから*2

\begin{align} \left|\left\langle f-\left.\mathbb{E}(f\right|\mathcal{B}''), G-\left.\mathbb{E}(G\right|\mathcal{B}'')\right\rangle\right| &\leq \int_{\mathbb{Z}_N}\left|f-\left.\mathbb{E}(f\right|\mathcal{B}'')\right| \cdot \left|G-\left.\mathbb{E}(G\right|\mathcal{B}'')\right| \\ &\leq \int_{\mathbb{Z}_N}\left|G-\left.\mathbb{E}(G\right|\mathcal{B}'')\right| \leq \left\|G-\left.\mathbb{E}(G\right|\mathcal{B}'')\right\|_{L^{\infty}}\ll \varepsilon\end{align}

なので、k, \delta, X, Fに依存して\varepsilonを十分小さく取れば

\displaystyle \left|\left\langle \left.\mathbb{E}(f\right|\mathcal{B}'')-\left.\mathbb{E}(f\right|\mathcal{B}'), \left.\mathbb{E}(G\right|\mathcal{B}'')-\left.\mathbb{E}(G\right|\mathcal{B}')\right\rangle\right| \gg_{k, \delta, X, F}1

とできる。Gは有界なので \left.\mathbb{E}(G\right|\mathcal{B}'') 及び \left.\mathbb{E}(G\right|\mathcal{B}') も有界である。L^2-ノルムのCauchy-Schwarzの不等式と三角不等式によって

\begin{align} \left|\left\langle \left.\mathbb{E}(f\right|\mathcal{B}'')-\left.\mathbb{E}(f\right|\mathcal{B}'), \left.\mathbb{E}(G\right|\mathcal{B}'')-\left.\mathbb{E}(G\right|\mathcal{B}')\right\rangle\right| &\leq \left\|\left.\mathbb{E}(f\right|\mathcal{B}'')-\left.\mathbb{E}(f\right|\mathcal{B}')\right\|_{L^2}\left\|\left.\mathbb{E}(G\right|\mathcal{B}'')-\left.\mathbb{E}(G\right|\mathcal{B}')\right\|_{L^2}\\ &\leq 2\left\|\left.\mathbb{E}(f\right|\mathcal{B}'')-\left.\mathbb{E}(f\right|\mathcal{B}')\right\|_{L^2}\end{align}

なので、

\displaystyle \left\|\left.\mathbb{E}(f\right|\mathcal{B}'')-\left.\mathbb{E}(f\right|\mathcal{B}')\right\|_{L^2}\gg_{k, \delta, X, F}1

であり、エネルギーギャップ公式より

\displaystyle \mathcal{E}_f(\mathcal{B}'')-\mathcal{E}_f(\mathcal{B}') \gg_{k, \delta, X, F} 1

が示された。これがエネルギー増加である。§6(その三)の複雑度の定義と\varepsilonの選び方、G \in B(UAP^{k-2})より、\mathcal{B}''の複雑度はO_{F, k, \delta, X, X'}(1)以下である。 Q.E.D.

(再掲) 構造定理 (Theorem 3.5) k \geq 3を整数とし、非負値有界関数 f\colon \mathbb{Z}_N \to \mathbb{R}^+は或る 0 < \delta \leq 1に対して条件
\displaystyle \int_{\mathbb{Z}_N}f \geq \delta
を満たすと仮定する。更に F \colon \mathbb{R}^+ \to \mathbb{R}^+を任意の関数とする。このとき、或る正の数 M=O_{k, \delta, F}(1), 有界関数 f_U \colon \mathbb{Z}_N \to \mathbb{C}, 非負値有界関数 f_{U^{\perp}}, \ f_{UAP} \colon \mathbb{Z}_N \to \mathbb{R}^+が存在して、
\begin{align}&\cdot \ f=f_U+f_{U^{\perp}}, \quad \cdot \ \left\| f_{U^{\perp}}-f_{UAP} \right\|_{L^2} \leq  \frac{\delta^2}{1024k},\quad \cdot \ \int_{\mathbb{Z}_N}f_{U^{\perp}} \geq \delta,\\ &\cdot \ \left\|f_{UAP}\right\|_{UAP^{k-2}} < M, \quad \cdot \ \left\|f_U\right\|_{U^{k-1}} \leq \frac{1}{F(M)}\end{align}
が成り立つ。

構造定理の証明

構造定理ダイコトミーに対して§7のエネルギー増加法を適用すればよい。ただし、d=k-2, \ m=1であること、\tau=\delta^2/2048kであること、及びLandauの記号(Vinogradovの記号)にパラメータFが追加されていることに注意(パラメータが増えれば、全てのLandauの記号にそのパラメータを付ければ証明が問題なく回るので、帰結となるLandauの記号にもそのパラメータをつければよい。実際、証明においてパラメータdは本質的な役割を果たしていなかった)。 Q.E.D.

*1:f_U=f_1+f_2, \ G=G_1+G_2+G_3とすると、内積の線型性より

\begin{align}\left\langle f_U, G\right\rangle &= \left\langle f_1+f_2, G_1+G_2+G_3\right\rangle \\ &=\left\langle f_1, G_1\right\rangle+\left\langle f_1, G_2\right\rangle+\left\langle f_1, G_3\right\rangle+\left\langle f_2, G_1\right\rangle+\left\langle f_2, G_2\right\rangle+\left\langle f_2, G_3\right\rangle\end{align}
であり、確認した諸性質から
\left\langle f_1, G_2\right\rangle=\left\langle f_1, G_3\right\rangle=\left\langle f_2, G_1\right\rangle=\left\langle f_2, G_3\right\rangle=0
が言える。例えば、G_2は\mathcal{B}''-可測なので \left.\mathbb{E}(G_2\right|\mathcal{B}'')=G_2 であり、条件付き期待値作用素の随伴性から
\left\langle f_1, G_2\right\rangle=\left\langle f_1, \left.\mathbb{E}(G_2\right|\mathcal{B}'')\right\rangle=\left\langle \left.\mathbb{E}(f_1\right|\mathcal{B}''), G_2\right\rangle=0
を得る( f_1は\mathcal{B}''と直交)。

*2:f_Uが有界であることと同じ理由。

タオのセメレディ論文の§7を読む

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

§7 The energy incrementation argument ではエネルギーを定義し、構造定理(Thm 3.5)と構造化回帰定理(Thm 3.3)の証明で用いるエネルギー増加法を抽象的な形で用意します。

定義 (エネルギー) 関数の組 \boldsymbol{f}=(f_1, \dots, f_m) \in \mathrm{Map}(\mathbb{Z}_N, \mathbb{C})^m と \mathbb{Z}_N上の\sigma-加法族 \mathcal{B} に対して、エネルギー \mathcal{E}_{\boldsymbol{f}}(\mathcal{B}) \in \mathbb{R}^+ を
\displaystyle \mathcal{E}_{\boldsymbol{f}}(\mathcal{B}) := \sum_{j=1}^m\left\|\left.\mathbb{E}(f_j\right|\mathcal{B})\right\|_{L^2}^2
と定義する。

§6(その一)の補題５より, エネルギーは自明な評価

\displaystyle 0 \leq \mathcal{E}_{\boldsymbol{f}}(\mathcal{B}) \leq \sum_{j=1}^m\left\|f_j\right\|_{L^2}^2 −①

を持ちます。

エネルギーギャップ公式 \mathcal{B}'を\mathbb{Z}_N上の\sigma-加法族とし、\mathcal{B}をその部分\sigma-加法族とする。このとき、
\displaystyle \mathcal{E}_{\boldsymbol{f}}(\mathcal{B}')-\mathcal{E}_{\boldsymbol{f}}(\mathcal{B}) = \sum_{j=1}^m\left\|\left.\mathbb{E}(f_j\right|\mathcal{B}')-\left.\mathbb{E}(f_j\right|\mathcal{B})\right\|_{L^2}^2
が成り立つ。特に、\mathcal{E}_{\boldsymbol{f}}(\mathcal{B}') \geq \mathcal{E}_{\boldsymbol{f}}(\mathcal{B}) とエネルギーが増加することがわかる。

証明. §6(その一)の補題３を使えば、補題５と同様にして勾股弦の定理

\displaystyle \left\|\left.\mathbb{E}(f_j\right|\mathcal{B}')\right\|_{L^2}^2-\left\|\left.\mathbb{E}(f_j\right|\mathcal{B})\right\|_{L^2}^2 = \left\|\left.\mathbb{E}(f_j\right|\mathcal{B}')-\left.\mathbb{E}(f_j\right|\mathcal{B})\right\|_{L^2}^2

を示すことができる。これを j=1, \dots, m で足し合わせれば所望のギャップ公式が得られる。 Q.E.D.

それでは、証明したい命題をダイコトミー*1に帰着させるエネルギー増加法を抽象的に用意しておきます。定理を一気には証明できない場合は、証明を完了させるためのエネルギーを溜めていくという手法です(エネルギーが上限に達すると証明が完了せざるを得ない)。

補題 (抽象的エネルギー増加法, Lemma 7.2) 整数 d \geq 0 と有界関数の組 \boldsymbol{f}=(f_1, \dots, f_m) \in \mathrm{Map}(\mathbb{Z}_N, \mathbb{C})^m を考え、P(M)を実数 M > 0 に依存する或る性質とする(真か偽が定まるもの)。もし、実数 \tau > 0 が存在して次のダイコトミー：

ダイコトミー データ

  1. 整数 X, \ X' \geq 0
  2. \mathcal{B}: 複雑度が高々Xのd-コンパクトな\mathbb{Z}_N上の\sigma-加法族
  3. \mathcal{B}': 複雑度が高々X'のd-コンパクトな\mathbb{Z}_N上の\sigma-加法族

であって、以下の二条件

  1. \sigma-加法族として \mathcal{B} \subset \mathcal{B}'
  2. (エネルギーギャップ条件) \mathcal{E}_{\boldsymbol{f}}(\mathcal{B}')-\mathcal{E}_{\boldsymbol{f}}(\mathcal{B}) \leq \tau^2 –②

を満たすものに対して、必ず次のいずれかが成り立つ：

  1. 或るM=O_{d, \tau, X, X'}(1)が存在して P(M)は真である。
  2. 複雑度が高々O_{d, \tau, X, X'}(1)のd-コンパクトな\mathbb{Z}_N上の\sigma-加法族 \mathcal{B}''であって \mathcal{B}'' \supset \mathcal{B}'を満たすものが存在して、以下のエネルギー増加が生じる：

\mathcal{E}_{\boldsymbol{f}}(\mathcal{B}'')-\mathcal{E}_{\boldsymbol{f}}(\mathcal{B}') \gg_{d, \tau, X}1 –③.

が成立するならば、或る M=O_{m, d, \tau}(1) に対して P(M) は真となる。

証明. 以下のようなd-コンパクト\sigma-加法族のペア(\mathcal{B}, \mathcal{B}')を構成する二重反復アルゴリズムを考える：

  1. 初期化\mathcal{B}:=自明な\sigma-加法族\{\emptyset, \mathbb{Z}_N\}
  2. 代入X:=\mathcal{B}の複雑度
  3. 初期化\mathcal{B}':=\mathcal{B}
  4. 代入X':=\mathcal{B}'の複雑度
  5. if 或る M=O_{d, \tau, X, X'}(1)に対してP(M)は真 then 停止
  6. else ダイコトミーによって存在する(\mathcal{B}\subset \mathcal{B}'とエネルギーギャップ条件②を満たしていることに注意)複雑度が高々O_{d, \tau, X, X'}(1)のd-コンパクトな\mathbb{Z}_N上の\sigma-加法族であってエネルギー増加③を満たす\mathcal{B}'' \supset \mathcal{B}'を一つ取る。
  7. if \mathcal{E}_{\boldsymbol{f}}(\mathcal{B}'')-\mathcal{E}_{\boldsymbol{f}}(\mathcal{B})\leq \tau^2 then 代入 \mathcal{B}':=\mathcal{B}'' (\mathcal{B} \subset \mathcal{B}'とエネルギー条件②は保たれる), 4. へ
  8. else 代入 \mathcal{B}:=\mathcal{B}'', 2. へ

Claim このアルゴリズムは時間O_{m, d, \tau}(1)で停止し、停止時の\mathcal{B}及び\mathcal{B}'の複雑度は高々O_{m, d, \tau}(1)にしか到達しない。

Sub-claim１ \mathcal{B}が固定されているときに\mathcal{B}'が変更される回数は高々O_{d, \tau, X}(1)回である。

理由: \mathcal{B}'が変更される際、ダイコトミーによってエネルギーが少なくとも\gg_{d, \tau, X}1だけ増大される。そうして、エネルギーが\mathcal{E}_{\boldsymbol{f}}(\mathcal{B})+\tau^2を超えると\mathcal{B}は変更されるのだから、\mathcal{B}が変更されるまでの\mathcal{B}'の変更回数は高々O_{d, \tau, X}(1)回である(回数の上限をd, \tau, Xだけで計算できる)。

Sub-claim２ 複雑度Xの\mathcal{B}が変更されると、変更後の複雑度は高々O_{d, \tau, X}(1)である。

理由: 複雑度X'の\mathcal{B}'が変更されると複雑度は高々O_{d, \tau, X, X'}(1)となるが、\mathcal{B}'の初期値は\mathcal{B}なので最初の変更では複雑度は高々O_{d, \tau, X}(1)にしかならない。ということは二回目の変更でも高々O_{d, \tau, X}(1)ということになる。そうして、\mathcal{B}一定時における\mathcal{B}'の変更回数がO_{d, \tau, X}(1)回(Sub-claim１)とX'に依らないので、結局複雑度は高々O_{d, \tau, X}(1)である。

Sub-claim３ \mathcal{B}が変更される回数は高々O_{m, \tau}(1)回である。

理由: \mathcal{B}が一回変更される度にエネルギー\mathcal{E}_{\boldsymbol{f}}(\mathcal{B})は少なくとも\tau^2増加される。しかし、f_j 達は有界関数であるのだから、エネルギーの自明な評価①によってエネルギーはmを超えることが許されない。従って、\mathcal{B}は\tauとmで決まる回数しか変更されない。

Claimの証明: \mathcal{B}の変更回数をnとし、各\mathcal{B}を順に\mathcal{B}_0, \dots, \mathcal{B}_nと名付ける。Sub-claim３より n=O_{m, \tau}(1)である。各0 \leq i \leq nに対して、\mathcal{B}_iの複雑度をX_i、\mathcal{B}'の変更回数をa_iとすれば、Sub-claim１よりa_i=O_{d, \tau, X_i}(1)である。Sub-claim２より

\displaystyle X_0=0, \quad X_i=O_{d, \tau, X_{i-1}}(1)

なので、n=O_{m, \tau}(1)と合わせて、任意の0 \leq i \leq nに対して X_i=O_{m, d, \tau}(1)である。従って、a_i=O_{m, d, \tau}(1)であり、アルゴリズムが停止するまでに現れるペア(\mathcal{B}, \mathcal{B}')の個数(アルゴリズムの"時間"を厳密に定義することは本質的なことではなく、適当に時間を定義すればペアの個数の定数倍で押さえられる)は

\displaystyle \sum_{i=0}^n(a_i+1)=nO_{m, d, \tau}(1)=O_{m, d, \tau}(1)

と評価できることが示された。既に示したように、停止時の\mathcal{B}である\mathcal{B}_nの複雑度はX_n=O_{m, d, \tau}(1)であり、a_n=O_{m, d, \tau}(1)とSub-claim２の議論から停止時の\mathcal{B}'の複雑度もO_{m, d, \tau}(1)であることがわかる。

Claimにより、停止時の(\mathcal{B}, \mathcal{B}')に対して X=O_{m, d, \tau}(1), X'=O_{m, d, \tau}(1)であり、停止条件から或る M=O_{d, \tau, X, X'}(1)=O_{m, d, \tau}(1)でP(M)が真となることが従う。 Q.E.D.


なお、この証明手法はカラフルな車輪を用いたvan der Waerdenの定理の証明と同じ構造をしています。

integers.hatenablog.com

その証明は同色k-APが見つけられなければカラフルな車輪のスポークの数を増やし、いつかはスポーク数の限界に達するというものでした。すなわち、

同色k-AP or スポーク数増加

のダイコトミーによる証明で、

スポーク数増加 ↔︎ エネルギー増加

の類似性があることがわかります。

*1:dichotomy. 日本語訳は"二分法"となるらしいですが、数値解析に二分法という専門用語があるのでかぶる危険性があります。私個人の経験として二分法という用語を頻繁に聞くこともない一方でTaoのword選択も尊重したいので、ここではカタカナ表記することにします。

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

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

前の記事では一様概周期関数に対して良い\mathbb{Z}_N上の\sigma-加法族が存在することを示しましたが、この記事では複数の一様概周期関数によって生成される\mathbb{Z}_N上の\sigma-加法族について議論します。

定義 (Definition 6.4) 整数 d \geq 0に対して、\mathbb{Z}_N上の\sigma-加法族\mathcal{B}がd-コンパクトであるとは

  1. \displaystyle X \geq 0, \ 0 \leq r \leq X \quad (X , \ r \in \mathbb{Z}),
  2. \displaystyle \frac{1}{X+1} \leq \varepsilon_1, \dots, \varepsilon_r \leq 1,
  3. G_1, \dots, G_r \in UAP^{d} \quad \left(\left\|G_j\right\|_{UAP^d}\leq X \ (1 \leq j \leq r)\right)

が存在して、

\displaystyle \mathcal{B}=\mathcal{B}_{\varepsilon_1}(G_1)\vee \cdots \vee \mathcal{B}_{\varepsilon_r}(G_r)

と書けるときにいう(r=0の場合は\mathcal{B}=\{\emptyset, \mathbb{Z}_N\})。また、d-コンパクトな\mathbb{Z}_N上の\sigma-加法族\mathcal{B}の(d-)複雑度を上記定義によって存在するXの最小値とする。

d-コンパクトでない\sigma-加法族のd-複雑度は\inftyと定義します。

補題 nを正の整数とする。1 \leq j \leq nに対する実数 0 \leq a_j, b_j \leq 1に対して、不等式
\displaystyle \left| \prod_{j=1}^na_j-\prod_{j=1}^nb_j \right| \leq \sum_{j=1}^n\left|a_j-b_j\right|
が成立する。

証明. n=2のときを示せば十分(一般の場合は帰納法)*1。 三角不等式と\left|b_1\right|, \left|a_2\right| \leq 1より

\begin{align} \left|a_1a_2-b_1b_2\right| &= \left|\det\begin{pmatrix}a_1 & b_1 \\ b_2 & a_2\end{pmatrix}\right|= \left|\det\begin{pmatrix}a_1-b_1 & b_1 \\ b_2-a_2 & a_2\end{pmatrix}\right| \\ &\leq \left|a_1-b_1\right| \left|a_2\right|+\left|b_1\right|\left|a_2-b_2\right| \leq \left|a_1-b_1\right|+\left|a_2-b_2\right|\end{align}

と評価できる。 Q.E.D.

コンパクトな\sigma-加法族上可測な関数であれば、一様概周期関数による良い近似が存在します：

命題 (コンパクト\sigma-加法族における一様概周期関数の稠密性, Proposition 6.6) d \geq 0, \ X \geq 0を整数、0 < \delta \leq 1を実数とする。\mathcal{B}を複雑度が高々Xのd-コンパクトな\mathbb{Z}_N上の\sigma-加法族とし、fを非負値有界\mathcal{B}-可測関数とする。このとき、非負値有界関数 f_{UAP} \in UAP^dが存在して、
\displaystyle \left\|f-f_{UAP}\right\|_{L^2} \leq \delta
かつ
\displaystyle \left\|f_{UAP}\right\|_{UAP^d} \ll_{\delta, X} 1
が成り立つ。

証明. \mathcal{B}に対して定義によって存在するデータ1. 2. 3. をとり、\mathcal{B}のアトムからなる集合を\mathrm{Atom}(\mathcal{B})とする。複雑度0の場合は自明なので、r \geq 1としてよい。このとき、§6を読む(その一)の補題４及び§6を読む(その二)の命題により

\displaystyle \#\mathrm{Atom}(\mathcal{B}) \leq \prod_{j=1}^r\#\mathrm{Atom}\left(\mathcal{B}_{\varepsilon_j}(G_j)\right) = \prod_{j=1}^rO_{X, \varepsilon_j}(1) = O_X(1)

である。これに注意すれば、§6を読む(その二)の命題の証明と全く同じ理由で f=\mathbf{1}_A(Aは\mathcal{B}のアトム)の場合に帰着される。A \in \mathrm{Atom}(\mathcal{B})を固定すると、§6を読む(その一)の補題４より \mathcal{B}_{\varepsilon_j}(G_j)のアトム A_jが存在して

A=A_1 \cap \cdots \cap A_r −①

と書ける。また、§6を読む(その二)の命題によって、各1 \leq j \leq rに対して非負値有界関数 f_{UAP}^{(j)} \in UAP^dが存在して

\displaystyle \left\|\mathbf{1}_{A_j}-f_{UAP}^{(j)}\right\|_{L^2} \leq \frac{\delta}{r}, \quad \left\|f_{UAP}^{(j)}\right\|_{UAP^d} = O_{\frac{\delta}{r}, \varepsilon_j, X}(1) = O_{\delta, X}(1)

が成り立つ。そこで、\displaystyle f_{UAP}:=\prod_{j=1}^rf_{UAP}^{(j)} としよう。これは明らかに非負値有界関数。UAP^dの積閉性よりf_{UAP} \in UAP^dであり

\displaystyle \left\|f_{UAP}\right\|_{UAP^d} \leq O_{\delta, X}(1)^r = O_{\delta, X}(1)

が成立する。補題より

\displaystyle \left|\prod_{j=1}^r\mathbf{1}_{A_j}-\prod_{j=1}^rf_{UAP}^{(j)}\right| \leq \sum_{j=1}^r\left|\mathbf{1}_{A_j}-f_{UAP}^{(j)}\right|

という評価が成り立つので、①とL^2-ノルムの定義・三角不等式より

\begin{align} \left\|\mathbf{1}_{A}-f_{UAP}\right\|_{L^2} &= \left\|\prod_{j=1}^r\mathbf{1}_{A_j}-\prod_{j=1}^rf_{UAP}^{(j)}\right\|_{L^2} \leq \left\|\sum_{j=1}^r\left|\mathbf{1}_{A_j}-f_{UAP}^{(j)}\right|\right\|_{L^2} \\ &\leq \sum_{j=1}^r\left\|\mathbf{1}_{A_j}-f_{UAP}^{(j)}\right\|_{L^2} \leq r\times \frac{\delta}{r} = \delta\end{align}

が得られ、証明が完了する。 Q.E.D.

*1:ここに紹介する証明は松森先生によります。私は最初次のように証明していました：a_1 \geq b_1, \ a_2 \geq b_2のとき。 a_1a_2 \geq b_1b_2に注意する。0 \geq a_1-1 \geq b_1-1 及び 0 \geq a_2-1 \geq b_2-1 なので

(a_1-1)(a_2-1) \leq (b_1-1)(b_2-1)
であり、
a_1a_2-b_1b_2 \leq (a_1-b_1)+(a_2-b_2)
が示された。 a_1 \geq b_1, \ a_2 \leq b_2のとき。 a_1+1 \geq b_1+1 > 0 及び a_2 -1 \leq b_2-1 \leq 0 なので
(a_1+1)(a_2-1) \leq (b_1+1)(b_2-1)
であり、
a_1a_2-b_1b_2 \leq (a_1-b_1)+(b_2-a_2).
また、 0 \geq a_1-1 \geq b_1-1 及び 0< a_2 +1 \leq b_2+1 なので
(a_1-1)(a_2+1) \geq (b_1-1)(b_2+1)
であり、
b_1b_2-a_1a_2 \leq (a_1-b_1)+(b_2-a_2).
つまり、
\displaystyle \left|a_1a_2-b_1b_2\right| \leq (a_1-b_1)+(b_2-a_2)
が示された。残り二つのケースはこの二つのケースから従う。