グリーン・タオの定理8 ハイパーグラフ除去補題の証明④~数え上げ補題~
こんにちは,itouです.今回は数え上げ補題の証明の解説をします.
この記事ではデータ$(M_0,F,(\mathcal B_e)_{e\in E})$を固定し,このデータに対し正則化補題を適用して得られる$((M_j)_{j\in[r],((\mathcal B_f,\mathcal B'_f))_{f\in\bigcup_{j\in[r]}\partial^jE}})$を1組とって固定します.(ただし対数をとったときに1以上であるように$F(1)\geq 3$としておく)
また,$\mathcal H$を以下とします.
表記
$\mathcal H=\bigcup_{j\in[0,r]}\partial^jE$とする.
これは$E$から作った$V_J$の部分集合族で,$E$の情報をうまく引き出してくれているのです.
数え上げ補題は$\bigvee_{e\in\mathcal H}\mathcal B_e$のアトム$A$に対して,$V_J$の元が$A$に入る確率を与えるものです.しかし,そのように確立を計算できるアトムには条件があります.
アトムの族のなす集合$\prod_{e\in\mathcal H}\rm{Atom}(\mathcal B_e)$を
\begin{align}
\prod_{e\in\mathcal H}\rm{Atom}(\mathcal B_e)=
\left( \prod_{e\in\mathcal H}\rm{Atom}(\mathcal B_e)\right)_{good} \cup
\left( \prod_{e\in\mathcal H}\rm{Atom}(\mathcal B_e)\right)_{bad}
\end{align}
と分ける.ただし,$(A_e)_{e\in\mathcal H}\in (\prod_{e\in\mathcal H}\rm{Atom}(\mathcal B_e))_{good}$であるのは任意の$j\in[0,r-1],e\in\partial^jE$に対して
\begin{align}
\mathbb E \left(
\mathbf1_{A_e}\prod_{f\in\partial e}\mathbf1_{A_f}\bigg|V_J
\right)\geq\frac{1}{\log F(M_j)}\mathbb E\left(\prod_{f\in \partial e}\mathbf1_{A_f}\bigg|V_J\right) \tag{1}\label{1}\\
\end{align}
および
\begin{align}
\mathbb E \left(
|b_e(A_e)|^2\prod_{f\in\subsetneq e}\mathbf1_{A_f}\bigg|V_J
\right)\leq\frac{1}{F(M_j)}\mathbb E\left(\prod_{f\in \subsetneq e}\mathbf1_{A_f}\bigg|V_J\right)\tag{2}\label{2}
\end{align}
が成り立っているときと定める.
\begin{align}
b_e(A_e)=\mathbb E\left(\mathbf1_{A_e}\bigg|\bigvee_{f\in\partial e}\mathcal B'_f\right)-\mathbb E\left(\mathbf1_{A_e}\bigg|\bigvee_{f\in\partial e}\mathcal B_f\right)
\end{align}
とおいた($V_J$上の関数であることに注意).
$(\prod_{e\in\mathcal H}\rm{Atom}(\mathcal B_e))_{bad}$は$(\prod_{e\in\mathcal H}\rm{Atom}(\mathcal B_e))_{good}$の補集合とする.
$(\prod_{e\in\mathcal H}\rm{Atom}(\mathcal B_e))_{good}$が数え上げ補題を適用可能なアトムたちです.かなり複雑な定義というか,ランダムに見えるようにしたいから頑張って条件を作ったという感じです.
以下のように定義しておきます.
\begin{align} B_{e,A_e}=\bigcup_{\text{$(A_f)_{f\subsetneq e}\in\prod_{f\subsetneq e}\rm{Atom}(\mathcal B_f)$で\ref{1}or\ref{2}が不成立なもの}}\left(\bigcap_{f\subsetneq e}A_f\right)\in \bigvee_{f\subsetneq e}\mathcal B_f \end{align}
うれしいことに,適用不可能なアトムたちは少ないことが分かります.
任意の$j\in[0,r-1],e\in\partial^jE,A_e\in\rm{\mathcal B_e}$に対して
\begin{align}
\mathbb E(\mathbf1_{A_e}\mathbf1_{B_{e,A_e}}|V_J)\leq \frac{2}{\log F(M_j)}
\end{align}
が成り立つ.
(証明略)
さて,数え上げ補題のステートメントを見てみましょう.
$k$のみに依存する関数$G_{CL;k}:\mathbb Z_{>0}\rightarrow\mathbb Z_{>0}$が存在して,以下が成立する.各点で$F\geq G_{CL:k}$であれば,$(\prod_{e\in\mathcal H\rm{Atom}(\mathcal B_e)})_{good}$の任意の元$(A_e)_{e\in\mathcal H}
$に対して
\begin{align}
\mathbb E\left(\prod_{e\in \mathcal H}\mathbf1_{A_e}\bigg|V_J\right)=(1+o_{M_0\rightarrow\infty;k}(1))\prod_{e\in\mathcal H\backslash\{\varnothing\}}\mathbb E\left(\mathbf1_{A_{e}}\bigg|\bigcap_{f\in \partial e}A_f\right)
\end{align}
が成り立つ.ただし,$\cap_{f\in\partial e}A_f=\varnothing$の場合は$\mathbb E\left( \mathbf1_{A_e}|\cap_{f\in\partial e}A_f \right)=1$とする.
左辺
\begin{align}
\mathbb E\left(\prod_{e\in \mathcal H}\mathbf1_{A_e}\bigg|V_J\right)
\end{align}
は$V_J$の元がアトム$ \bigcap_{e\in\mathcal H}A_e$に属する確率だと解釈できます.一方,右辺の
\begin{align}
\mathbb E\left(\mathbf1_{A_{e}}\bigg|\bigcap_{f\in \partial e}A_f\right)
\end{align}
は$V_J$の元が$\bigcap_{f\in\partial e}A_f$に属するという条件の下でアトム$A_e$に属する確率を表し,数え上げ補題は近似式
\begin{align}
\mathbb E\left(\prod_{e\in \mathcal H}\mathbf1_{A_e}\bigg|V_J\right)\fallingdotseq\prod_{e\in\mathcal H\backslash\{\varnothing\}}\mathbb E\left(\mathbf1_{A_{e}}\bigg|\bigcap_{f\in \partial e}A_f\right)
\end{align}
が成立することを主張します.これは事象の独立性を言っています.一般に,事象の族$\{A_{\lambda}\}$が独立なとき,
\begin{align}
P(A_{\lambda_1}\cap\cdots\cdot A_{\lambda_n})=P(A_{\lambda_1})\cdots P(A_{\lambda_n})
\end{align}
でした.
つまり
「$V_J$の元がアトム$ \bigcap_{e\in\mathcal H}A_e$に属する確率」
は
「$e$ごとに$\bigcap_{f\in\partial e}A_f$に分けてから$A_e$に入るという事象に分割し,それらが独立であるとして計算した確率」
で近似できるということです.
これは正則化補題によってうまい分割構造を与え,ランダムグラフにみえるようにした効果が表れています.
以下,$(\prod_{e\in\mathcal H\rm{Atom}(\mathcal B_e)})_{good}$の元$(A_e)_{e\in\mathcal H}$を固定します.このとき,各$e\in\mathcal H\backslash \{\varnothing\}$について以下のように定義します.
$p_e\in\mathbb R,\ b_e,c_e:V_J\rightarrow\mathbb R,A_{\subsetneq e}\subset V_J$を
\begin{align}
&p_e=\mathbb E\left(\mathbf1_{A_e}\bigg|\bigcap_{
f\in\partial e}A_f\right)\\
&b_e=b_e(A_e)=\mathbb E\left(\mathbf1_{A_e}\bigg|\bigvee_{f\in\partial e}\mathcal B'_f\right)-\mathbb E\left(\mathbf1_{A_e}\bigg|\bigvee_{f\in\partial e}\mathcal B_f\right)\\
&c_e=\mathbf1_{A_e}-\mathbb E\left(\mathbf1_{A_e}\bigg|\bigvee_{f\in\partial e}\mathcal B'_f\right)\\
&A_{\subsetneq e}=\bigcap_{f\subsetneq \partial e}A_f
\end{align}
とおく.ただし,$\bigcap_{
f\in\partial e}A_f=\varnothing$の場合は$p_e=1$とする.
これらについての道具を用意します.
$e\in \mathcal H\backslash\{\varnothing\}$に対して以下が成り立つ.
(1)任意の$x\in\bigcap_{f\in\partial e}A_f$に対して,$\mathbf1_{A_e}(x)=p_e+b_e(x)+c_e(x)$.
(2)$e\in\partial^jE$のとき,$p_e\geq\frac{1}{\log F(M_j)}$.
(3)$e\in\partial^jE$のとき,
\begin{align}
\quad\mathbb E(|b_e|^2\mathbf1_{A_{\subsetneq e}}|V_J)\leq\frac{1}{F(M_j)}\mathbb E(\mathbf1_{A_{\subsetneq e}}|V_J).
\end{align}
(4)任意の$(E_f)_{f\in\partial e}\in\prod_{f\in\partial e}A_f$に対して,
\begin{align}
\quad \left|E\left(c_e\prod_{f\in\partial e}\mathbf1_{E_f}\bigg|V_J\right)\right|\leq \frac{1}{F(M_j)}.
\end{align}
ある関数$G_{CL;k}:\mathbb Z_{>0}\rightarrow\mathbb Z_{>0}$が存在して,$F\geq G_{CL:k}$であれば
\begin{align}
\mathbb E\left(\prod_{e\in \mathcal H}\mathbf1_{A_e}\bigg|V_J\right)=(1+o_{M_0\rightarrow\infty;k}(1))\prod_{e\in\mathcal H\backslash\{\varnothing\}}p_e
\end{align}
であることを示したいです.
さて,$e\in\mathcal H$に対して,$A_e\in \mathcal B_e\subset \mathcal A_e$に対応する$V_e=\prod_{j\in e}V_j$の部分集合を$\overline{A_e}=\pi_e(A_e)$と略記する$(\overline{A_{\varnothing}}=\varnothing)$.$f\in\mathcal M(\mathcal A_e)$であるとき,任意の$x\in\mathbb E$に対して$f^{-1}(\{x\})\in\mathcal A_e$であることに注意すると,下の図式を可換にする$\overline{f}$が一意に存在することがわかる.
$e\in\mathcal \backslash\{\varnothing\}$に対して
\begin{align}
\mathbb E\left(\mathbf1_{A_e}\bigg|\bigvee_{f\in\partial e}\mathcal B_f\right)\in\mathcal M\left(\bigvee_{f\in\partial e}\mathcal A_e\right)\subset\mathcal M\left(\bigvee_{f\in\partial e}\mathcal A_e\right)
\subset \mathcal M(\mathcal A_e)
\end{align}
などに注意して,$b_e,c_e\in\mathcal M(\mathcal A_e)$がわかるので,対応する$V_e$から$\mathbb R$への写像を$\overline{b_e},\overline{c_e}$と表す.
1つ目の記事でファン・デル・ヴェルデンの定理をグラハム・ロスチャイルドの定理に一般化して示しました.同様に,数え上げ補題を一般化を経由して示します.
組$(K,\mathcal G,\rm{pr})$が$\mathcal H$上の束であるとは,$K$が有限集合,$\mathcal G\subset \mathfrak P(K),\rm{pr}:K\rightarrow J$であり,任意の$g\in\mathcal G$に対しては$\rm{pr}$は$g$上に制限すると単射であり,$\rm{pr}(g)\in\mathcal H$が成り立ち,部分集合$g'\subset g$に対して$g'\in\mathcal G$が成り立つときをいう.
$\mathcal G$の次元(または束$(K,\mathcal G,\rm{pr})$の次元)を$\rm{dim}\mathcal G=\max_{g\in\mathcal G}\sharp g$と定義する.
表記
$g\subset K$に対して,$V_g^{(K)}=\prod_{i\in g}V_{\rm{pr}(i)}$とする($V_{\varnothing}^{(K)}=\varnothing$)
また,$x=(x_i)_{i\in K}\in V_{K}^{(K)}$に対して$x_g=(x_i)_{i\in g}\in V_g^{(K)}$と略記する.
$(K,\mathcal G,\rm{pr})$を$\mathcal H$上の束とし,$\rm{dim}\mathcal G=d\geq 0$とする.このとき,$d,\sharp K$のみに依存する関数$G_{GCL;d,\sharp K}:\mathbb Z_{>0}\rightarrow\mathbb Z_{>0}$が存在して,以下が成立する.各点で$F\geq G_{GCL;d,\sharp K}$であれば,
\begin{align}
\mathbb E\left(\prod_{g\in \mathcal G}\mathbf1_{\overline{A_{\rm{pr(g)}}}}(x_g)\bigg|x\in V_K^{(K)}\right)=
(1+o_{M_0\rightarrow\infty;d,\sharp K}(1))\prod_{g\in\mathcal G}p_{\rm{pr}(g)}
\end{align}
が成り立つ.ただし,$p_{\varnothing}=1$とする.
この記事を高評価した人
この記事に送られたバッジ
投稿者
