グリーン・タオの定理8　ハイパーグラフ除去補題の証明④~数え上げ補題~

この著者は初心者として投稿しています。間違いや考慮が足りていない点が含まれている可能性が高いです。見つけたらコメント欄で優しく指摘してあげましょう。

こんにちは,itouです.今回は数え上げ補題の証明の解説をします.

この記事ではデータ $(M_{0}, F, (B_{e})_{e \in E})$ を固定し,このデータに対し正則化補題を適用して得られる $((M_{j})_{j \in [r], ((B_{f}, B_{f}^{'}))_{f \in ⋃_{j \in [r]} \partial^{j} E}})$ を1組とって固定します.(ただし対数をとったときに1以上であるように $F (1) \geq 3$ としておく)
　また, $H$ を以下とします.

表記

$H = ⋃_{j \in [0, r]} \partial^{j} E$ とする.

これは $E$ から作った $V_{J}$ の部分集合族で, $E$ の情報をうまく引き出してくれているのです.

数え上げ補題は $\underset{e \in H}{⋁} B_{e}$ のアトム $A$ に対して, $V_{J}$ の元が $A$ に入る確率を与えるものです.しかし,そのように確立を計算できるアトムには条件があります.

数え上げ補題を適用可能なアトム

アトムの族のなす集合 $\prod_{e \in H} A t o m (B_{e})$ を

$\begin{array}{r} \prod_{e \in H} A t o m (B_{e}) = {(\prod_{e \in H} A t o m (B_{e}))}_{g o o d} \cup {(\prod_{e \in H} A t o m (B_{e}))}_{b a d} \end{array}$
と分ける.ただし, $(A_{e})_{e \in H} \in (\prod_{e \in H} A t o m (B_{e}))_{g o o d}$ であるのは任意の $j \in [0, r - 1], e \in \partial^{j} E$ に対して
$\begin{array}{r} (1) & E (1_{A_{e}} \prod_{f \in \partial e} 1_{A_{f}} | V_{J}) \geq \frac{1}{\log F (M_{j})} E (\prod_{f \in \partial e} 1_{A_{f}} | V_{J}) \end{array}$
および
$\begin{array}{r} (2) & E (| b_{e} (A_{e}) |^{2} \prod_{f \in⊊ e} 1_{A_{f}} | V_{J}) \leq \frac{1}{F (M_{j})} E (\prod_{f \in⊊ e} 1_{A_{f}} | V_{J}) \end{array}$
が成り立っているときと定める.
$\begin{array}{r} b_{e} (A_{e}) = E (1_{A_{e}} | \underset{f \in \partial e}{⋁} B_{f}^{'}) - E (1_{A_{e}} | \underset{f \in \partial e}{⋁} B_{f}) \end{array}$
とおいた( $V_{J}$ 上の関数であることに注意).
$(\prod_{e \in H} A t o m (B_{e}))_{b a d}$ は $(\prod_{e \in H} A t o m (B_{e}))_{g o o d}$ の補集合とする.

$(\prod_{e \in H} A t o m (B_{e}))_{g o o d}$ が数え上げ補題を適用可能なアトムたちです.かなり複雑な定義というか,ランダムに見えるようにしたいから頑張って条件を作ったという感じです.
　以下のように定義しておきます.

B_{e, A_{e}}

$\begin{array}{r} B_{e, A_{e}} = ⋃_{(A_{f})_{f ⊊ e} \in \prod_{f ⊊ e} A t o m (B_{f}) で 1 or 2 が不成立なもの} (⋂_{f ⊊ e} A_{f}) \in \underset{f ⊊ e}{⋁} B_{f} \end{array}$

うれしいことに,適用不可能なアトムたちは少ないことが分かります.

数え上げ補題を適用不可能なアトムたちの割合は小さい

任意の $j \in [0, r - 1], e \in \partial^{j} E, A_{e} \in B_{e}$ に対して
$\begin{array}{r} E (1_{A_{e}} 1_{B_{e, A_{e}}} | V_{J}) \leq \frac{2}{\log F (M_{j})} \end{array}$
が成り立つ.

(証明略)
さて,数え上げ補題のステートメントを見てみましょう.

数え上げ補題

$k$ のみに依存する関数 $G_{C L; k} : Z_{> 0} \to Z_{> 0}$ が存在して,以下が成立する.各点で $F \geq G_{C L : k}$ であれば, $(\prod_{e \in H A t o m (B_{e})})_{g o o d}$ の任意の元 $(A_{e})_{e \in H}$ に対して
$\begin{array}{r} E (\prod_{e \in H} 1_{A_{e}} | V_{J}) = (1 + o_{M_{0} \to \infty; k} (1)) \prod_{e \in H ∖ {\emptyset}} E (1_{A_{e}} | ⋂_{f \in \partial e} A_{f}) \end{array}$
が成り立つ.ただし, $\cap_{f \in \partial e} A_{f} = \emptyset$ の場合は $E (1_{A_{e}} | \cap_{f \in \partial e} A_{f}) = 1$ とする.

左辺
$\begin{array}{r} E (\prod_{e \in H} 1_{A_{e}} | V_{J}) \end{array}$
は $V_{J}$ の元がアトム $⋂_{e \in H} A_{e}$ に属する確率だと解釈できます.一方,右辺の
$\begin{array}{r} E (1_{A_{e}} | ⋂_{f \in \partial e} A_{f}) \end{array}$
は $V_{J}$ の元が $⋂_{f \in \partial e} A_{f}$ に属するという条件の下でアトム $A_{e}$ に属する確率を表し,数え上げ補題は近似式

$\begin{array}{r} E (\prod_{e \in H} 1_{A_{e}} | V_{J}) ≒ \prod_{e \in H ∖ {\emptyset}} E (1_{A_{e}} | ⋂_{f \in \partial e} A_{f}) \end{array}$
が成立することを主張します.これは事象の独立性を言っています.一般に,事象の族 ${A_{λ}}$ が独立なとき,

$\begin{array}{r} P (A_{λ_{1}} \cap \dots \cdot A_{λ_{n}}) = P (A_{λ_{1}}) \dots P (A_{λ_{n}}) \end{array}$
でした.

つまり
「 $V_{J}$ の元がアトム $⋂_{e \in H} A_{e}$ に属する確率」
は
「 $e$ ごとに $⋂_{f \in \partial e} A_{f}$ に分けてから $A_{e}$ に入るという事象に分割し,それらが独立であるとして計算した確率」
で近似できるということです.

これは正則化補題によってうまい分割構造を与え,ランダムグラフにみえるようにした効果が表れています.
以下, $(\prod_{e \in H A t o m (B_{e})})_{g o o d}$ の元 $(A_{e})_{e \in H}$ を固定します.このとき,各 $e \in H ∖ {\emptyset}$ について以下のように定義します.

p_{e}, b_{e}, c_{e}

$p_{e} \in R, b_{e}, c_{e} : V_{J} \to R, A_{⊊ e} \subset V_{J}$ を
$\begin{aligned} p_{e} = E (1_{A_{e}} | ⋂_{f \in \partial e} A_{f}) \\ b_{e} = b_{e} (A_{e}) = E (1_{A_{e}} | \underset{f \in \partial e}{⋁} B_{f}^{'}) - E (1_{A_{e}} | \underset{f \in \partial e}{⋁} B_{f}) \\ c_{e} = 1_{A_{e}} - E (1_{A_{e}} | \underset{f \in \partial e}{⋁} B_{f}^{'}) \\ A_{⊊ e} = ⋂_{f ⊊ \partial e} A_{f} \end{aligned}$
とおく.ただし, $⋂_{f \in \partial e} A_{f} = \emptyset$ の場合は $p_{e} = 1$ とする.

これらについての道具を用意します.

p_{e}, b_{e}, c_{e}

について

$e \in H ∖ {\emptyset}$ に対して以下が成り立つ.

(1)任意の $x \in ⋂_{f \in \partial e} A_{f}$ に対して, $1_{A_{e}} (x) = p_{e} + b_{e} (x) + c_{e} (x)$ .
(2) $e \in \partial^{j} E$ のとき, $p_{e} \geq \frac{1}{\log F (M_{j})}$ .
(3) $e \in \partial^{j} E$ のとき,
$\begin{array}{r} E (| b_{e} |^{2} 1_{A_{⊊ e}} | V_{J}) \leq \frac{1}{F (M_{j})} E (1_{A_{⊊ e}} | V_{J}) . \end{array}$

(4)任意の $(E_{f})_{f \in \partial e} \in \prod_{f \in \partial e} A_{f}$ に対して,
$\begin{array}{r} | E (c_{e} \prod_{f \in \partial e} 1_{E_{f}} | V_{J}) | \leq \frac{1}{F (M_{j})} . \end{array}$

ある関数 $G_{C L; k} : Z_{> 0} \to Z_{> 0}$ が存在して, $F \geq G_{C L : k}$ であれば
$\begin{array}{r} E (\prod_{e \in H} 1_{A_{e}} | V_{J}) = (1 + o_{M_{0} \to \infty; k} (1)) \prod_{e \in H ∖ {\emptyset}} p_{e} \end{array}$
であることを示したいです.
　さて, $e \in H$ に対して, $A_{e} \in B_{e} \subset A_{e}$ に対応する $V_{e} = \prod_{j \in e} V_{j}$ の部分集合を $\overset{―}{A_{e}} = π_{e} (A_{e})$ と略記する $(\overset{―}{A_{\emptyset}} = \emptyset)$ . $f \in M (A_{e})$ であるとき,任意の $x \in E$ に対して $f^{- 1} ({x}) \in A_{e}$ であることに注意すると,下の図式を可換にする $\overset{―}{f}$ が一意に存在することがわかる.
$e \in ∖ {\emptyset}$ に対して
$\begin{array}{r} E (1_{A_{e}} | \underset{f \in \partial e}{⋁} B_{f}) \in M (\underset{f \in \partial e}{⋁} A_{e}) \subset M (\underset{f \in \partial e}{⋁} A_{e}) \subset M (A_{e}) \end{array}$
などに注意して, $b_{e}, c_{e} \in M (A_{e})$ がわかるので,対応する $V_{e}$ から $R$ への写像を $\overset{―}{b_{e}}, \overset{―}{c_{e}}$ と表す.

1つ目の記事でファン・デル・ヴェルデンの定理をグラハム・ロスチャイルドの定理に一般化して示しました.同様に,数え上げ補題を一般化を経由して示します.

束

組 $(K, G, p r)$ が $H$ 上の束であるとは, $K$ が有限集合, $G \subset P (K), p r : K \to J$ であり,任意の $g \in G$ に対しては $p r$ は $g$ 上に制限すると単射であり, $p r (g) \in H$ が成り立ち,部分集合 $g^{'} \subset g$ に対して $g^{'} \in G$ が成り立つときをいう.
$G$ の次元(または束 $(K, G, p r)$ の次元)を $d i m G = max_{g \in G} ♯ g$ と定義する.

表記

$g \subset K$ に対して, $V_{g}^{(K)} = \prod_{i \in g} V_{p r (i)}$ とする( $V_{\emptyset}^{(K)} = \emptyset$ )
また, $x = (x_{i})_{i \in K} \in V_{K}^{(K)}$ に対して $x_{g} = (x_{i})_{i \in g} \in V_{g}^{(K)}$ と略記する.

数え上げ補題の一般化

$(K, G, p r)$ を $H$ 上の束とし, $d i m G = d \geq 0$ とする.このとき, $d, ♯ K$ のみに依存する関数 $G_{G C L; d, ♯ K} : Z_{> 0} \to Z_{> 0}$ が存在して,以下が成立する.各点で $F \geq G_{G C L; d, ♯ K}$ であれば,
$\begin{array}{r} E (\prod_{g \in G} 1_{\overset{―}{A_{p r (g)}}} (x_{g}) | x \in V_{K}^{(K)}) = (1 + o_{M_{0} \to \infty; d, ♯ K} (1)) \prod_{g \in G} p_{p r (g)} \end{array}$
が成り立つ.ただし, $p_{\emptyset} = 1$ とする.