インテジャーズ

INTEGERS

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

ハイパーグラフ除去補題ー4

定義 記事3の正則化補題の記号・仮定・帰結を考え、\mathcal{H}:=\bigcup_{0 \leq j \leq d}H_jとする。各e \in \mathcal{H}に対して、\mathcal{B}_eのアトムA_eをとる。このとき、\displaystyle \bigcap_{e \in \mathcal{H}}A_e(これは空集合か\bigvee_{e \in \mathcal{H}}\mathcal{B}_eのアトム)がgoodであるとは、任意の0 \leq j \leq dおよびe \in H_jに対して次の二つの評価が成り立つときにいう:

\displaystyle \mathbb{E}\Bigl(\mathbf{1}_{A_e}\prod_{f \in \partial e}\mathbf{1}_{A_f}\Bigr) \geq \frac{1}{\log F(M_j)}\mathbb{E}\Bigl(\prod_{f \in \partial e}\mathbf{1}_{A_f}\Bigr) −①

\displaystyle \mathbb{E}\Bigl( \Big| \ \mathbb{E}\Bigl(\mathbf{1}_{A_e} \ \Big| \ \bigvee_{f \in \partial e}\mathcal{B}_f'\Bigr) - \mathbb{E}\Bigl( \mathbf{1}_{A_e} \ \Big| \ \bigvee_{f \in \partial e}\mathcal{B}_f \Bigr) \ \Big|^2 \prod_{f \subsetneq e}\mathbf{1}_{A_f}\Bigr) \leq \frac{1}{F(M_j)}\mathbb{E}\Bigr(\prod_{f \subsetneq e}\mathbf{1}_{A_f}\Bigr) −②

\log Fが負となるような状況は扱わない。0 \leq j \leq d, \ e \in H_j, \mathcal{B}_eのアトムA_eに対して、B_{e, A_e}

\displaystyle B_{e, A_e} := \bigcup_{\substack{\{A_f\}_{f \subsetneq e}, \ A_f \in \mathrm{Atom}(\mathcal{B}_f) \\ \text{① or ② 不成立}}}\Bigl(\bigcap_{f \subsetneq e}A_f\Bigr) \in \bigvee_{f \subsetneq e}\mathcal{B}_f

と定める。\displaystyle \bigcap_{e' \in \mathcal{H}}A_{e'}がgoodでなければ、或るe \in \mathcal{H}が存在して

\displaystyle \bigcap_{e' \in \mathcal{H}}A_{e'} \subset A_e \cap B_{e, A_e}

が成り立つ。次の補題は殆どのアトムはgoodであることを意味する。

補題 正則化補題の記号・仮定・帰結および上記記号設定を考える。このとき、任意の0 \leq j \leq d, e \in H_jおよび\mathcal{B}_eのアトムA_eに対して
\displaystyle \mathbb{E}\left(\mathbf{1}_{A_e}\mathbf{1}_{B_{e, A_e}}\right) = O\left(\frac{1}{\log F(M_j)}\right)
が成り立つ。

証明. 定義より

\displaystyle B_{e, A_e} \subset \bigcup_{\substack{\{A_f\}_{f \in \partial e}, \ A_f \in \mathrm{Atom}(\mathcal{B}_f) \\ \text{① 不成立}}}\Bigl(\bigcap_{f \in \partial e}A_f\Bigr) \cup \bigcup_{\substack{\{A_f\}_{f \subsetneq e}, \ A_f \in \mathrm{Atom}(\mathcal{B}_f) \\ \text{② 不成立}}}\Bigl(\bigcap_{f \subsetneq e}A_f\Bigr)

が成り立つので、

\displaystyle \mathbb{E}\left(\mathbf{1}_{A_e}\mathbf{1}_{B_{e, A_e}}\right) \leq \sum_{\substack{\{A_f\}_{f \in \partial e}, \ A_f \in \mathrm{Atom}(\mathcal{B}_f) \\ \text{① 不成立}}}\mathbb{E}\Bigl(\mathbf{1}_{A_e}\prod_{f \in \partial e}\mathbf{1}_{A_f}\Bigr) + \sum_{\substack{\{A_f\}_{f \subsetneq e}, \ A_f \in \mathrm{Atom}(\mathcal{B}_f) \\ \text{② 不成立}}}\mathbb{E}\Bigl(\mathbf{1}_{A_e}\prod_{f \subsetneq e}\mathbf{1}_{A_f}\Bigr)

と評価できる。一つ目の和は

\displaystyle \sum_{\substack{\{A_f\}_{f \in \partial e}, \ A_f \in \mathrm{Atom}(\mathcal{B}_f) \\ \text{① 不成立}}}\mathbb{E}\Bigl(\mathbf{1}_{A_e}\prod_{f \in \partial e}\mathbf{1}_{A_f}\Bigr) < \sum_{\{A_f\}_{f \in \partial e}, \ A_f \in \mathrm{Atom}(\mathcal{B}_f)}\frac{1}{\log F(M_j)}\mathbb{E}\Bigl(\prod_{f \in \partial e}\mathbf{1}_{A_f}\Bigr) \leq \frac{1}{\log F(M_j)}

と評価できる。二つ目の和は

\begin{align} &\sum_{\substack{\{A_f\}_{f \subsetneq e}, \ A_f \in \mathrm{Atom}(\mathcal{B}_f) \\ \text{② 不成立}}}\mathbb{E}\Bigl(\mathbf{1}_{A_e}\prod_{f \subsetneq e}\mathbf{1}_{A_f}\Bigr) \leq \sum_{\substack{\{A_f\}_{f \subsetneq e}, \ A_f \in \mathrm{Atom}(\mathcal{B}_f) \\ \text{② 不成立}}}\mathbb{E}\Bigl(\prod_{f \subsetneq e}\mathbf{1}_{A_f}\Bigr) \\ &< \sum_{\{A_f\}_{f \subsetneq e}, \ A_f \in \mathrm{Atom}(\mathcal{B}_f)}F(M_j)\mathbb{E}\Bigl( \Big| \ \mathbb{E}\Bigl(\mathbf{1}_{A_e} \ \Big| \ \bigvee_{f \in \partial e}\mathcal{B}_f'\Bigr) - \mathbb{E}\Bigl( \mathbf{1}_{A_e} \ \Big| \ \bigvee_{f \in \partial e}\mathcal{B}_f \Bigr) \ \Big|^2 \prod_{f \subsetneq e}\mathbf{1}_{A_f}\Bigr) \\ &\leq F(M_j)\mathbb{E}\Bigl( \Big| \ \mathbb{E}\Bigl(\mathbf{1}_{A_e} \ \Big| \ \bigvee_{f \in \partial e}\mathcal{B}_f'\Bigr) - \mathbb{E}\Bigl( \mathbf{1}_{A_e} \ \Big| \ \bigvee_{f \in \partial e}\mathcal{B}_f \Bigr) \ \Big|^2\Bigr)\end{align}

と評価できるが、正則化補題より

\displaystyle \mathcal{E}_{A_e}\Bigl(\bigvee_{f \in \partial e}\mathcal{B}_f'\Bigr)-\mathcal{E}_{A_e}\Bigl(\bigvee_{f \in \partial e}\mathcal{B}_f\Bigr) \leq \frac{1}{F(M_j)^2}

が成り立つので、エネルギーギャップ公式と合わせて

\displaystyle \sum_{\substack{\{A_f\}_{f \subsetneq e}, \ A_f \in \mathrm{Atom}(\mathcal{B}_f) \\ \text{② 不成立}}}\mathbb{E}\Bigl(\mathbf{1}_{A_e}\prod_{f \subsetneq e}\mathbf{1}_{A_f}\Bigr) \leq \frac{1}{F(M_j)}

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

定理 (カウンティング補題) 正則化補題の記号・仮定・帰結および定義の設定を考える。\displaystyle \bigcap_{e \in \mathcal{H}}A_eはgoodであると仮定する。F\colon \mathbb{R}_{>0} \to \mathbb{R}_{>0}\#Jに依存して十分成長速度の速い関数であれば、
\displaystyle \mathbb{E}\Bigl(\prod_{e \in \mathcal{H}}\mathbf{1}_{A_e}\Bigr) = \left(1+o_{M_d \to \infty; \#J}(1)\right)\prod_{e \in \mathcal{H}}\mathbb{E}\Bigl(\mathbf{1}_{A_e} \ \Big| \ \bigcap_{f \in \partial e}A_f\Bigr) + O_{\#J, M_0}\left(\frac{1}{F(M_0)}\right)
が成り立つ。

\bigcap_{f \in \partial e}A_f=\emptysetのときは\mathbb{E}\Bigl(\mathbf{1}_{A_e} \ \Big| \ \bigcap_{f \in \partial e}A_f\Bigr)=1とする。カウンティング補題の証明は後回しにして、ハイパーグラフ除去補題の証明を先に完了させる。

定理 (ハイパーグラフ除去補題、再掲) V=(J, (V_j)_{j \in J}, d, H)をハイパーグラフ系とする。ハイパーエッジe \in H毎にE_e \in \mathcal{A}_eであって、0 < \delta < 1に対して
\displaystyle \mathbb{E}\Bigl(\prod_{e \in H}\mathbf{1}_{E_e}\Bigr) \leq \delta
が成り立つようなものをとる。このとき、各e \in Hに対して或るE_e' \in \mathcal{A}_eが存在して
\displaystyle \bigcap_{e \in H}E_e' = \emptyset,\quad \mathbb{E}\Bigl(\mathbf{1}_{E_e \setminus E_e'}\Bigr) = o_{\delta \to 0; \#J}(1)
が成り立つ。更に、e' \subset J, \ \#e' < dに対して部分\sigma加法族\mathcal{B}_{e'} \subset \mathcal{A}_{e'}が存在して、\mathrm{cpx}(\mathcal{B}_{e'}) = O_{\delta, \#J}(1)かつ任意のe \in Hに対して
\displaystyle E_e' \in \bigvee_{e' \subsetneq e}\mathcal{B}_{e'}
が成り立つ。

カウンティング補題 \Longrightarrow ハイパーグラフ除去補題の証明. ハイパーグラフ除去補題の設定を考える(「このとき、」の直前まで)。0 \leq j \leq dに対してH_jH_d:=H, H_j:=\partial H_{j+1} \ (0 \leq j < d)で定める。\displaystyle \mathcal{H}:=\bigcup_{0 \leq j \leq d}H_jとする。各e \in H_dに対して、\mathcal{B}_e:= \mathcal{B}(E_e) \subset \mathcal{A}_eとする(E_eが生成するV_J上の\sigma加法族)。\mathrm{cpx}(\mathcal{B}_e) \leq 1である。

M_d \geq 1\delta, \#Jに依存して後で決まる整数とする(\mathrm{cpx}(\mathcal{B}_e) \leq M_dは成立している)。また、F\colon \mathbb{R}_{>0} \to \mathbb{R}_{>0}は正則化補題および後の議論で要求されるだけ十分成長速度の速い、\#Jのみに依存して定まる関数とする。

以上の設定で正則化補題を適用することによって存在するM_0, M_1, \dots, M_{d-1}および(\mathcal{B}_f, \mathcal{B}_f') \ ({}^{\forall}f \in H_j \ (0 \leq j < d) )をとる。この\mathcal{B}_f達が除去補題が後半に主張する\sigma加法族となる(証明はこれから)。次の不等式を思い出しておく。

M_d \leq F(M_d) \leq M_{d-1} \leq F(M_{d-1}) \leq \cdots \leq M_0 \leq F(M_0) \leq O_{\#J, M_d, F}(1)

後のM_d, Fの選択によって、\mathrm{cpx}(\mathcal{B}_f) \leq M_j = O_{\#J, M_d, F}(1) = O_{\delta, \#J}(1)が約束されている。

e \in H_dに対して、E_e'

\displaystyle E_e' := V_J \setminus \Bigl( B_{e, E_e} \cup \bigcup_{f \subsetneq e}\bigcup_{A_f \in \mathrm{Atom}(\mathcal{B}_f)}(A_f \cap B_{f, A_f})\Bigr)

と定義する。定義より、\displaystyle E_e' \in \bigvee_{f \subsetneq e}\mathcal{B}_f \subset \mathcal{A}_eがわかる。

\displaystyle E_e\setminus E_e' = E_e \cap \Bigl(B_{e, E_e} \cup \bigcup_{f \subsetneq e}\bigcup_{A_f \in \mathrm{Atom}(\mathcal{B}_f)}(A_f \cap B_{f, A_f})\Bigr)

なので、補題より

\begin{align} \mathbb{E}(\mathbf{1}_{E_e\setminus E_e'}) &\leq \mathbb{E}(\mathbf{1}_{E_e}\mathbf{1}_{B_{e, E_e}})+\sum_{f \subsetneq e}\sum_{A_f \in \mathrm{Atom}(\mathcal{B}_f)}\mathbb{E}(\mathbf{1}_{A_f}\mathbf{1}_{B_{f, A_f}}) \\ &\leq O\left(\frac{1}{\log F(M_d)}\right) + \sum_{0 \leq j < d}\sum_{f \in H_j}\sum_{A_f \in \mathrm{Atom}(\mathcal{B}_f)}O\left(\frac{1}{\log F(M_j)}\right)\end{align}

と評価できる。各0 \leq j < d, f \in H_jに対して\#\mathrm{Atom}(\mathcal{B}_f)\leq 2^{\mathrm{cpx}(\mathcal{B}_f)} \leq 2^{M_j}なので、

\displaystyle  \mathbb{E}(\mathbf{1}_{E_e\setminus E_e'})  \leq \max_{0 \leq j \leq d}O_{M_j, \#J}\left(\frac{1}{\log F(M_j)}\right)

が得られるが、M_j達の中でM_dが最小であることから、F\#Jに依存して十分成長速度が速ければ

 \mathbb{E}(\mathbf{1}_{E_e\setminus E_e'}) =o_{M_d \to \infty; \#J}(1)

が成り立つことがわかる。後でわかるように\delta \to 0であればM_d \to 0となるようにM_dは選択されるため、

 \mathbb{E}(\mathbf{1}_{E_e\setminus E_e'}) =o_{\delta \to \infty; \#J}(1)

が示されたことになる。後は示すべきことは\displaystyle \bigcap_{e \in H_d}E_e' = \emptysetのみである。そこで、\displaystyle \bigcap_{e \in H_d}E_e' \neq \emptysetと仮定して、\displaystyle \bigcap_{e \in H_d}E_e'に含まれるアトムを一つとる。\displaystyle \bigcap_{e \in H_d}E_e' \in \bigvee_{f \in \mathcal{H}\setminus H_d}\mathcal{B}_fなので、それは\displaystyle \bigcap_{f \in \mathcal{H}\setminus H_d}A_fという形をしている(A_f \in \mathrm{Atom}(\mathcal{B}_f))。このA_f達を固定した上で、e \in H_dに対してはA_e:=E_eとする。このとき、\displaystyle \bigcap_{e \in \mathcal{H}}A_eはgoodではない。

理由: goodであったと仮定すると、カウンティング補題よりF\#Jに依存して十分成長速度が速ければ

\displaystyle \mathbb{E}\Bigl(\mathbf{1}_{\bigcap_{e \in \mathcal{H}}A_e}\Bigr) = \left(1+o_{M_d \to \infty; \#J}(1)\right)\prod_{e \in \mathcal{H}}\mathbb{E}\Bigl(\mathbf{1}_{A_e} \ \Big| \ \bigcap_{f \in \partial e}A_f\Bigr) + O_{\#J, M_0}\left(\frac{1}{F(M_0)}\right)

が成り立つ。goodの定義の①より0 \leq j \leq dおよびe \in H_jに対して

\displaystyle \mathbb{E}\Bigr(\mathbf{1}_{A_e} \ \Big| \ \bigcap_{f \in \partial e}A_f\Bigr) = \frac{\mathbb{E}\Bigl(\mathbf{1}_{A_e}\prod_{f \in \partial e}\mathbf{1}_{A_f}\Bigr)}{\mathbb{E}\Bigl(\prod_{f \in \partial e}\mathbf{1}_{A_f}\Bigr)} \geq \frac{1}{\log F(M_j)}

が成り立つので、F\#Jに依存して十分成長速度が速ければ

\displaystyle \prod_{e \in \mathcal{H}}\mathbb{E}\Bigl(\mathbf{1}_{A_e} \ \Big| \ \bigcap_{f \in \partial e}A_f\Bigr)  \geq \frac{1}{(\log F(M_0) )^{\#\mathcal{H}}} \geq \frac{1}{\sqrt{F(M_0)}}

と評価できる。O_{\#J, M_0}の定数をc(\#J, M_0)とすれば、F\#Jに依存して十分成長速度が速く、M_d\#Jに依存して十分大きければ

\displaystyle\mathbb{E}\Bigl(\mathbf{1}_{\bigcap_{e \in \mathcal{H}}A_e}\Bigr)\geq \frac{1}{2\sqrt{F(M_0)}}-\frac{c(\#J, M_0)}{F(M_0)} \geq \frac{1}{3\sqrt{F(M_0)}}

を得る。Fはこの時点で決定されている。F(M_0)=O_{\#J, M_d, F}(1) = O_{\#J, M_d}(1)なので、M_d \geq {}^{\exists}N(\#J)であれば、或るC(\#J, M_d) > 0が存在して

\displaystyle\mathbb{E}\Bigl(\mathbf{1}_{\bigcap_{e \in \mathcal{H}}A_e}\Bigr)\geq C(\#J, M_d)

が成り立つことがわかった。整数M_d \geq N(\#J)に対する関数C(\#J, M_d) (< 1)は狭義単調減少かつ\displaystyle \lim_{M_d \to \infty}C(\#J, M_d) = 0であると仮定してよい。\deltaに対するM_dの選択は、M_d \geq N(\#J)かつ

\displaystyle C(\#J, M_d) > \delta \geq C(\#J, M_d+1)

を満たすものと定める。\deltaが(\#Jに依存して)大きいとこのようなM_dは決まらないが、目標に\displaystyle \mathbb{E}\left(\mathbf{1}_{E_e \setminus E_e'}\right) = o_{\delta \to 0; \#J}(1)という漸近挙動がある以上、そのような\deltaについてはE_e':=\emptyset, M_d=1と考えて問題ない。そうして、

\displaystyle C(\#J, M_d) \leq \mathbb{E}\Bigl(\mathbf{1}_{\bigcap_{e \in \mathcal{H}}A_e}\Bigr) \leq \mathbb{E}\Bigl(\mathbf{1}_{\bigcap_{e \in H_d}E_e} \Bigr) \leq \delta

となって矛盾する

よって、\displaystyle \bigcap_{e \in \mathcal{H}}A_eはgoodではないので、定義より或る f' \in \mathcal{H}が存在して

\displaystyle \bigcap_{g \subsetneq f'}A_g \subset B_{f', A_{f'}}

が成り立つことがわかる。f' \subset e'なるe' \in H_dをとる(\mathcal{H}の定義)。このとき、

\displaystyle \bigcap_{f \in \mathcal{H}\setminus H_d}A_f \subset \bigcap_{g \subsetneq f'}A_g \subset B_{f', A_{f'}}

なので、f'\subsetneq e'であれば

\displaystyle \bigcap_{f \in \mathcal{H}\setminus H_d}A_f \subset (A_{f'} \cap B_{f', A_{f'}})

であるし、f'=e'であっても

\displaystyle \bigcap_{f \in \mathcal{H}\setminus H_d}A_f \subset B_{e', A_{e'}}

となって、定義より

\displaystyle \bigcap_{f \in \mathcal{H}\setminus H_d}A_f \not \subset E_{e'}'

が言える。しかし、

\displaystyle \bigcap_{f \in \mathcal{H}\setminus H_d}A_f \subset \bigcap_{e \in H_d}E_e'

であったため矛盾する。 Q.E.D.