タオのセメレディ論文の§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$ が存在して次のダイコトミー：

ダイコトミー データ

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

であって、以下の二条件

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

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

或る $M=O_{d, \tau, X, X'}(1)$ が存在して $P(M)$ は真である。
複雑度が高々 $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}')$ を構成する二重反復アルゴリズムを考える：

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