グリーン・タオの定理7 ハイパーグラフ除去補題の証明③ ～正則化補題～
こんにちは,itouです.今回はハイパーグラフ除去補題の証明に用いる正則化補題の解説をしていきます.
気持ちとしては,グラフに含まれるハイパーグラフを除去するためにその個数を数え上げたいので,グラフに上手く分割構造を与えることでランダムグラフのようにします(正則化補題).ランダムグラフなら数えやすいからです.そのように正則化したグラフを数え上げるのが数え上げ補題です.
今回は正則化補題を解説していきます.すべての補題,命題の証明はせず,重要な部分のみ解説します.
正則化補題
定義,補題
まだ新しい言葉が出てくるのかと思いますが,今までの内容の延長にすぎません.
$J$の部分集合$e\in J$に対して,$e$の骨格$\partial e$を
\begin{align}
\partial e=\{f\in \mathfrak B(e):\sharp f=\sharp e-1 \}
\end{align}
と定義する.また,集合$R\subset \mathfrak B(J)\backslash \{\varnothing\}$に対して,$\partial R$を
\begin{align}
\partial R=\bigcup_{e\in R}\partial e
\end{align}
と定義する.さらに,$j\in[0,r]$に対して,$\partial^jE$を$\partial E^0=E,\partial^{j+1}E=\partial(\partial^jE),(j\in[0,r-1])$と帰納的に定義する.
$J=\{1,2,3,4\}$とする.
$e=\{1,2\}$とすると
$\partial e=\{\{1\},\{2\}\}$
$e=\{2,3\}$とすると
$\partial e=\{\{2\},\{3\}\}$
$e=\{1,2,3\}$とすると
$\partial e=\{\{1,2\},\{2,3\},\{1,3\}\}$
$R=\{\{1,2\},\{2,3\},\{1,2,3\}\}$とすると,
$\partial R=\{\{1\},\{2\},\{3\},\{1,2\},\{2,3\},\{1,3\}\}$
今後は$e$に対する加法族を直接考えていくのでなく,$e$の骨格からできる加法族たちを用いて間接的に取り扱っていきます.
集合$e\subset J(e\ne \varnothing),A\subset V_J$および$V_J$上の加法族$\mathcal B$に対し,$\triangle_e(A|\mathcal B)$を
\begin{align}
\triangle_e(A|\mathcal B)=d_{\mathcal F}(\mathbf 1_A,\mathbb E(\mathbf 1_A)|\mathcal B)
\end{align}
と定義する.ただし,
\begin{align}
\mathcal F=\left\{ \bigcap_{f\in \partial e}E_f:\forall f\in \partial e,E_f\in \mathcal A \right\}
\end{align}
とし,$d_{\mathcal F}$は$L^2(V_J,\mathbb R)$上の$\mathcal F_e$に関する食い違い距離である.
食い違い$\triangle_e(A|\mathcal B)$が小さいとき,$A$は$\mathcal B$のほとんどのアトム上で「ランダムな」ように振る舞います.これが求めている状況です.
$A\subset V_J$と$V_J$上の加法族$\mathcal B$に対し,$\mathcal B$の$A$のエネルギー$\mathcal E_A(\mathcal B)$を
\begin{align}
\mathcal E_A(\mathcal B)=\|\mathbb E(\mathbf 1_A|\mathcal B)\|^2
\end{align}
と定義する.
$\mathcal B'$を$V$上の加法族,$\mathcal B$を$\mathcal B'$の部分加法族とする.このとき,$A\subset V_J$に対して,
\begin{align}
\mathcal E_A(\mathcal B')=\mathcal E_A(\mathcal B)+\|\mathbb E(\mathbf 1_A|\mathcal B)-\mathbb E(\mathbf1_A|\mathcal B)\|
\end{align}
が成り立つ.
(証明略)
正則化補題は反復アルゴリズムによって示されるのですが,エネルギーはそのための量です.
次の命題は食い違いがエネルギーを増加させることを示します.
$e\in J(e\ne \varnothing),E_e\in \mathcal A_e,\varepsilon>0$を考える.各$f\in \partial e$に対して$\mathcal A_f$の部分加法族であるような族$(\mathcal B_f)_{f\in \partial e}$があって,
\begin{align}
\triangle_e \left( E_e \bigg| \bigvee_{f\in \partial e} \mathcal B_f \right)\geq \varepsilon
\end{align}
を満たしているとする.このとき,各$f\in \partial e$に対して$\mathcal B'_f$が$\mathcal B_f\subset\mathcal B'_f\subset \mathcal A_f$を満たす$V_J$上の加法族であるような族$(\mathcal B'_f)_{f\in \partial e}$が存在して,任意の$f\in \partial e$に対して,任意の$f\in \partial e$に対して
\begin{align}
\rm{cpx}(\mathcal B'_f)\leq \rm{cpx}(\mathcal B_f)+1
\end{align}
であり,
\begin{align}
\mathcal E_{E_e}\left(\bigvee_{f\in \partial e}\mathcal B'_f\right)\geq \mathcal E_{E_e} \left(\bigvee_{f\in \partial e}\mathcal B_f \right)+\varepsilon^2
\end{align}
が成り立つ.
(証明略)
骨格からできる加法族たちについて,それらを細分すると複雑度は高々1しか増加せず,エネルギーが増加するということです.$\mathcal B_f$たちには「良い」分割が取れるのです.これが骨格を考える理由です.
前正則化補題
前正則化補題を示し,それにより正則化補題を示します.前正則化補題の主張は以下の通りです.
正整数$m$,正の実数$\varepsilon$,単調増大関数$F:\mathbb Z_{>0}\rightarrow\mathbb Z_{>0}$に対して,ある正整数$C=C_{PRL}(k,m,\varepsilon,F)$が存在して,以下が成立する.各$e\in E$ごとに$\rm{cpx}(\mathcal B_e)\leq m$を満たす$\mathcal A_e$の部分加法族$\mathcal B_e$をとる.このとき,ある$M\in [C]$および,各$f\in \partial E$について$\mathcal B_f\subset\mathcal B'_f\subset A_f$であるような$V_J$上の加法族のペアの族$((\mathcal B_f,\mathcal B'_f))_{f\in\partial E}$が存在して,以下が成立する.
(1)$F(m)\leq M$
(2)任意の$f\in\partial E$に対して,$\rm{cpx}(\mathcal B_f)\leq M$.
(3)任意の$e\in E,E_e\in\mathcal B_e$に対して,
\begin{align}
\mathcal E_{E_e}\left(\bigvee_{f\in \partial e}\mathcal B'_f\right)- \mathcal E_{E_e} \left(\bigvee_{f\in \partial e}\mathcal B_f \right)\geq\varepsilon^2
\end{align}
(4)任意の$e\in E,E_e\in\mathcal B_e$に対して,
\begin{align}
\triangle_e \left( E_e \bigg| \bigvee_{f\in \partial e} \mathcal B'_f \right)\leq \frac{1}{F(M)}.
\end{align}
$e$に対する加法族$\mathcal A_e$の部分加法族たちを$f\in\partial E$に対する加法族$\mathcal A_f$の部分加法族たちによって取り扱います.$\mathcal B_f$たちの細分を取っていくとエネルギーが増加するが,食い違いが小さくなってくれるようにできるということです.複雑度の条件はあまり気にしなくてよいです.これを反復アルゴリズムによって示します.
前正則化補題のアルゴリズム
前半
正整数$m$および正の実数$\varepsilon,\delta>0$に対して,ある正整数$C=C_{RS}(k,m,\varepsilon,\delta)$が存在して,以下が成立する.$M$を正整数,各$e\in E$に対して$\mathcal B_e$を$\mathcal A_e$の部分加法族であって$\rm{cpx}(\mathcal B_f)\leq m$を満たすもの,各$f\in \partial e$に対して$\mathcal B_f$を$\mathcal A_f$の部分加法族であって$\rm{cpx}(\mathcal B_f\leq M)$を満たすものとする.このとき,各$ f\in\partial E$に対して$\mathcal B'_f$に対して$\mathcal B'_f$が$\mathcal B_f\subset\mathcal B'_f\subset\mathcal A_f$を満たす$V_J$上の加法族であるような族$(\mathcal B'_f)_{f\in\partial E}$が存在して,以下のいずれかが成立する.
(状態1)任意の$e\in E$および$E_e\in \mathcal B_e$に対して
\begin{align}
\mathcal E_{E_e}\left(\bigvee_{f\in \partial e}\mathcal B'_f\right)\geq \mathcal E_{E_e} \left(\bigvee_{f\in \partial e}\mathcal B_f \right)+\varepsilon^2
\end{align}
および
\begin{align}
\triangle_e \left( E_e \bigg| \bigvee_{f\in \partial e}\mathcal B'_f \right)\leq \delta
\end{align}
が成り立つ.
(状態2)任意の$f\in\partial E$に対して
\begin{align}
\rm{cpx}(\mathcal B'_f)\leq M+C
\end{align}
であり,ある$e\in E$および$E_e\in\mathcal B_e$が存在して
\begin{align}
\mathcal E_{E_e}\left(\bigvee_{f\in \partial e}\mathcal B'_f\right)\geq \mathcal E_{E_e} \left(\bigvee_{f\in \partial e}\mathcal B_f \right)+\varepsilon^2
\end{align}
が成り立つ.
(状態1)か(状態2)のどちらかが実現されると停止するアルゴリズムを考えます.
$(\mathrm{i})$
$\mathcal B'_f=\mathcal B_f$と初期化する.
$(\mathrm{ii})$
任意の$e\in E$および$E_e\in \mathcal B_e$に対してが成立している場合,アルゴリズムを停止する.
$(\mathrm{iii})$
「食い違いが大きい」なら命題2より各$f\in\partial e$に対して$\mathcal B''_f$が$\mathcal B'_f\subset \mathcal B''_f\subset \mathcal A_f$を満たす加法族であるような族$(\mathcal B''_f)$が存在して,任意の$f\in\partial e$に対して$\rm{cpx}(\mathcal B''_f\leq\rm{cpx}(\mathcal B'_f)+1)$であり,
\begin{align}
\mathcal E_{E_e}\left(\bigvee_{f\in \partial e}\mathcal B'_f\right)\geq\mathcal E_{E_e} \left(\bigvee_{f\in \partial e}\mathcal B_f \right)+\delta^2
\end{align}
が成立.このような$e,E_e,(\mathcal B''_f)_{f\in\partial e}$を1つずつとって各$f\in\partial e$に対し$\mathcal B'_f=\mathcal B''_f$と更新する.
$\mathrm{(iv)}$
ある$e\in E$および$E_e\in\mathcal B_e$が存在してが成立している場合,アルゴリズムを停止する.
$\mathrm{(v)}$
任意の$e\in E$および$E_e\in\mathcal B_e$に対しが成立している場合,$(\mathrm{i})$へ
以上のアルゴリズムにより,必ず(状態1),(状態2)のいずれかが成立するようにできます.$(\mathrm{ii})$で停止すれば(状態1)です.
後半
正整数$m$,正の実数$\varepsilon$,単調増大関数$F:\mathbb Z_{>0}\rightarrow\mathbb Z_{>0}$に対して,ある正整数$C=C_{PRL}(k,m,\varepsilon,F)$が存在して,以下が成立する.各$e\in E$ごとに$\rm{cpx}(\mathcal B_e)\leq m$を満たす$\mathcal A_e$の部分加法族$\mathcal B_e$をとる.このとき,ある$M\in [C]$および,各$f\in \partial E$について$\mathcal B_f\subset\mathcal B'_f\subset A_f$であるような$V_J$上の加法族のペアの族$((\mathcal B_f,\mathcal B'_f))_{f\in\partial E}$が存在して,以下が成立する.
(1)$F(m)\leq M$
(2)任意の$f\in\partial E$に対して,$\rm{cpx}(\mathcal B_f)\leq M$.
(3)任意の$e\in E,E_e\in\mathcal B_e$に対して,
\begin{align}
\mathcal E_{E_e}\left(\bigvee_{f\in \partial e}\mathcal B'_f\right)- \mathcal E_{E_e} \left(\bigvee_{f\in \partial e}\mathcal B_f \right)\geq\varepsilon^2
\end{align}
(4)任意の$e\in E,E_e\in\mathcal B_e$に対して,
\begin{align}
\triangle_e \left( E_e \bigg| \bigvee_{f\in \partial e} \mathcal B'_f \right)\leq \frac{1}{F(M)}.
\end{align}
$(\mathrm{i})$
各$f\in\partial E$について,$\mathcal B_f=\{\varnothing,V_J\}$と初期化する.
$(\mathrm{ii})$
$M=\max\{F(m),\max_{f\in\partial E}\rm{cpx}(\mathcal B_f)\},\delta=1/F(M)$と代入する.データ$(m.\varepsilon,\delta,(\mathcal B_e)_{e\in E},(\mathcal B_f)_{f\in\partial E})$に対して前半を適用し,(状態1)または(状態2)が成立する$(\mathcal B'_f)_{f\in\partial E}$を1つとる.
$(\mathrm{iii})$
$(\mathrm{ii})$でとった$(\mathcal B'_f)_{f\in\partial E}$が(状態1)を満たしているならアルゴリズムを停止する.
$\mathrm{(iv)}$
$(\mathrm{ii})$でとった$(\mathcal B'_f)_{f\in\partial E}$が(状態2)を満たしているなら,各$f\in\partial E$に対して$\mathcal B_f=\mathcal B'_f$と代入.$(\mathrm{ii})$へ.
正整数$M$および$F(n)\geq n(n\in\mathbb Z_{>0})$を満たす単調増大関数$F:\mathbb Z_{>0}\rightarrow\mathbb Z_{>0}$に対して,ある正整数$C=C_{RL}(k,M,F)$が存在して,以下が成立する.各$e\in E$に対して$\mathcal B_e$を$\mathcal A_e$の部分加法族であって$\rm{cpx}(\mathcal B_e)\leq M$を満たすようなものとし,$M_0=M$とおく.このとき,
\begin{align}
M_0\leq F(M_0)\leq M_1\leq F(M_1)\leq\cdots\leq M_r\leq F(M_r)\leq C
\end{align}
を満たす整数列$(M_j)_{j\in [r]}$が存在し,さらに各$f\in \bigcup_{j\in [r]}\partial^jE$について$\mathcal B_f\subset\mathcal B'_f\subset A_f$であるような$V_J$上の加法族のペアの族$((\mathcal B_f,\mathcal B'_f))_{f\in\bigcup_{j\in[r]}\partial^j E}$が存在して,全ての$j\in [r],f\in \partial^jE$に対して
\begin{align}
\rm{cpx}(\mathcal B_f)\leq M_j
\end{align}
が成り立ち,全ての$j\in [0,r-1],e\in \partial^j E$および$E_e\in\mathcal B_e$に対して
\begin{align}
\mathcal E_{E_e}\left(\bigvee_{f\in \partial e}\mathcal B'_f\right)- \mathcal E_{E_e} \left(\bigvee_{f\in \partial e}\mathcal B_f \right)\leq\frac{1}{F(M_j)^2}
\end{align}
および
\begin{align}
\triangle_e \left( E_e \bigg| \bigvee_{f\in \partial e} \mathcal B'_f \right)\leq \frac{1}{F(M_r)}
\end{align}
が成り立つ.
証明
$r\in[k]$に関する数学的帰納法で証明する.ただし,$r$ごとにある正整数$C^{(r)}_{RL}(k,M,F)$が存在することを示し,最終的に$C_{RL}^{(r)}(k,M,F)=\max_{r\in[k]}C_{RL}^{r}(k,M,F)$とする.
関数$F'=F'(k,r,F):\mathbb Z_{>0}\rightarrow\mathbb Z_{>0}$を$r=1$のときは$F,r\geq2$のとき($r-1$における正則化補題の成立が仮定されているとき)は各$n\in\mathbb Z_{>0}$に対して
\begin{align}
F'(n)=\max\{F(n),\max_{l\in[n]}C^{r-1}_{RL}(k,l,m)\}
\end{align}
と定義する(これは単調増大).データ$(m,\varepsilon,F)$を$(M_0,F(M_0)^{-1},F')$として前正則化補題を適用すると,正整数$M_1$および$f\in\partial E$について$\mathcal B_f\subset\mathcal B'_f\subset \mathcal A_f$であるような$V_J$上の加法族のペアの族$((\mathcal B_f,\mathcal B'_f))_{f\in\partial E}$が存在して,以下が成立する.
(1)$F(M_0)\leq F'(M_0)\leq M_1\leq C_{PRL}(k,M_0,F(M_0)^{-1},F')$.
(2)任意の$f\in\partial E$に対して,$\rm{cpx}(\mathcal B_f)\leq M_1$.
(3)任意の$e\in E,E_e\in\mathcal B_e$に対して,
\begin{align}
\mathcal E_{E_e}\left(\bigvee_{f\in \partial e}\mathcal B'_f\right)- \mathcal E_{E_e} \left(\bigvee_{f\in \partial e}\mathcal B_f \right)\leq\frac{1}{F(M_0)^2}
\end{align}
(4)任意の$e\in E,E_e\in\mathcal B_e$に対して,
\begin{align}
\triangle_e \left( E_e \bigg| \bigvee_{f\in \partial e} \mathcal B'_f \right)\leq \frac{1}{F'(M_1)}
\end{align}
これで$r=1$のときは示された.実際,$C^(1)_{RL}(k,m,F)=F(C_{PRL}(k,M,F(M)^{-1},F))$とすればよい.以下,$r\geq 2$として$r-1$における正則化補題の成立を仮定する.
データ$(k,M_1,F)$および$(r-1)$グラフ型$((J,\partial E);(V_j)_{j\in J})$,上の$(\mathcal B_f)_{f\in\partial E}$に対して帰納法の仮定を適用して,
\begin{align}
M_1\leq F(M_1)\leq M_2\leq F(M_2)\leq\cdots\leq M_r\leq F(M_r)\leq C_{RL}^{(r-1)}(k,M_1,F)
\end{align}
を満たす整数列$(M_j)_{j\in [2,r]}$が存在し,さらに各$f\in \bigcup_{j\in [2,r]}\partial^jE$について$\mathcal B_f\subset\mathcal B'_f\subset A_f$であるような$V_J$上の加法族のペアの族$((\mathcal B_f,\mathcal B'_f))_{f\in\bigcup_{j\in[2,r]}\partial^j E}$が存在して,全ての$j\in [2,r],f\in \partial^jE$に対して
\begin{align}
\rm{cpx}(\mathcal B_f)\leq M_j
\end{align}
が成り立ち,全ての$j\in [r-1],e\in \partial^j E$および$E_e\in\mathcal B_e$に対して
\begin{align}
\mathcal E_{E_e}\left(\bigvee_{f\in \partial e}\mathcal B'_f\right)- \mathcal E_{E_e} \left(\bigvee_{f\in \partial e}\mathcal B_f \right)\leq\frac{1}{F(M_j)^2}
\end{align}
および
\begin{align}
\triangle_e \left( E_e \bigg| \bigvee_{f\in \partial e} \mathcal B'_f \right)\leq \frac{1}{F(M_r)}
\end{align}
が成り立つ.
このとき,$F'$の定義より
\begin{align}
F(M_r)\leq C^{(r-1)}_{RL}(k,M_1,F)\leq F'(M_1)
\end{align}
なので,$F'(M_1)^{-1}\leq F(M_r)^{-1}$が成立.また,
\begin{align} C_{RL}^{(r)}(k,M,F)=\max_{n\in[C_{PRL}(k,M,F(M)^{-1},F'(k,r,F))]}C_{RL}^{(r-1)}(k,n,F) \end{align}
と定めると,$C_{RL}^{(r-1)}(k,M_1,F)\leq C_{RL}^{(r)}(k,M_0,F)$である.したがって,$r$の場合も示された.
この記事を高評価した人
この記事に送られたバッジ
投稿者
