インテジャーズ

INTEGERS

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

タオのセメレディ論文の§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(その一)の補題5より, エネルギーは自明な評価

\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(その一)の補題3を使えば、補題5と同様にして勾股弦の定理

\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}: 複雑度が高々Xd-コンパクトな\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-claim1 \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-claim2 複雑度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-claim1)とX'に依らないので、結局複雑度は高々O_{d, \tau, X}(1)である

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

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

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

\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-claim2の議論から停止時の\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選択も尊重したいので、ここではカタカナ表記することにします。