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

この記事からハイパーグラフ除去補題を証明していく。ハイパーグラフ系 $V=(J, (V_j)_{j \in J}, d, H)$ を固定する。単に期待値を書いたら $V_J$ 上の期待値とする。

Terence Taoによる証明の方針は

integers.hatenablog.com

と非常に似ている。そこでも扱ったように、 $V_J$ 上の $\sigma$ 加法族 $\mathcal{B}$ と $f \colon V_J \to \mathbb{R}$ に対して条件付き期待値 $\mathbb{E}(f \mid \mathcal{B}) \colon V_J \to \mathbb{R}$ を

$\displaystyle \mathbb{E}(f \mid \mathcal{B})(x) := \frac{1}{\#\mathcal{B}(x)}\sum_{y \in \mathcal{B}(x)}f(y)$

で定義する。ここで、 $\mathcal{B}(x)$ は $x$ を含むような $\mathcal{B}$ のアトムを表す。

Discrepancyとエネルギー

定義１ $e \subset J$ に対して、 $\partial e$ を $\partial e := \{f \subsetneq e \mid \#f=\#e-1\}$ と定める。 $e \subset J, E_e \subset V_J$ , $V_J$ 上の $\sigma$ 加法族 $\mathcal{B}$ を考える。このとき、 $E_e$ の $\mathcal{B}$ に関する $e$ -discrepancy $\Delta_e(E_e \mid \mathcal{B})$ を

$\displaystyle \Delta_e(E_e \mid \mathcal{B}) := \max_{(E_f)_{f \in \partial e}, E_f \in \mathcal{A}_f}\left|\mathbb{E}\left( (\mathbf{1}_{E_e}-\mathbb{E}(\mathbf{1}_{E_e} \mid \mathcal{B}) )\prod_{f \in \partial e}\mathbf{1}_{E_f}\right)\right|$

と定義する。

定義２ $\mathcal{B}$ を $V_J$ 上の $\sigma$ 加法族とし、 $E\subset V_J$ を集合とする。このとき、 $\mathcal{B}$ の $E$ -エネルギー $\mathcal{E}_E(\mathcal{B})$ を

$\displaystyle \mathcal{E}_E(\mathcal{B}) := \mathbb{E}(\left|\mathbb{E}(\mathbf{1}_E \mid \mathcal{B})\right|^2)$

と定義する。

定義から明らかに $0 \leq \mathcal{E}_E(\mathcal{B}) \leq 1$ である。また、 $\sigma$ 加法族 $\mathcal{B} \subset \mathcal{B}'$ に対して、Tao-§6(1)の補題３より勾股弦の定理

$\displaystyle \left|\mathbb{E}(\mathbf{1}_E \mid \mathcal{B}')\right|^2 = \left|\mathbb{E}(\mathbf{1}_E \mid \mathcal{B})\right|^2+\left|\mathbb{E}(\mathbf{1}_E \mid \mathcal{B'})-\mathbb{E}(\mathbf{1}_E\mid \mathcal{B})\right|^2$

が成り立つので、エネルギーギャップ公式

$\displaystyle \mathcal{E}_E(\mathcal{B}') = \mathcal{E}_E(\mathcal{B})+\mathbb{E}\left(\left|\mathbb{E}(\mathbf{1}_E \mid \mathcal{B'})-\mathbb{E}(\mathbf{1}_E\mid \mathcal{B})\right|^2\right)$

が得られる。

補題１ (Discrepancyが引き起こすエネルギー増加) $e \subset J, E_e \in \mathcal{A}_e$ をとし、各 $f \in \partial e$ に対して $\sigma$ 加法族 $\mathcal{B}_f \subset \mathcal{A}_f$ であって、

$\displaystyle \Delta_e\Bigl(E_e \ \Big| \ \bigvee_{f \in \partial e}\mathcal{B}_f\Bigr) \geq \varepsilon$

が成り立つようなものをとる( $\varepsilon > 0$ )。このとき、任意の $f \in \partial e$ に対して、 $\mathcal{B}_f \subset \mathcal{B}_f' \subset \mathcal{A}_f$ となるような $\sigma$ 加法族 $\mathcal{B}_f'$ であって、 $\displaystyle \mathrm{cpx}(\mathcal{B}_f') \leq \mathrm{cpx}(\mathcal{B}_f)+1$ および

$\displaystyle \mathcal{E}_{E_e}\Bigl(\bigvee_{f \in \partial e}\mathcal{B}_f'\Bigr) \geq \mathcal{E}_{E_e}\Bigl(\bigvee_{f \in \partial e}\mathcal{B}_f\Bigr)+\varepsilon^2$

が成り立つようなものが存在する。

証明. $e$ -discrepancyの定義より任意の $f \in \partial e$ に対して或る $E_f \in \mathcal{A}_f$ が存在して、

$\displaystyle \left|\mathbb{E}\left(\Bigl(\mathbf{1}_{E_e}-\mathbb{E}\Bigl(\mathbf{1}_{E_e} \ \Big| \ \bigvee_{f \in \partial e}\mathcal{B}_f\Bigr) \Bigr)\prod_{f \in \partial e}\mathbf{1}_{E_f}\right) \right| \geq \varepsilon$

が成り立つ。これらを用いて、 $\mathcal{B}_f':=\mathcal{B}_f \vee \mathcal{B}(E_f)$ と各 $f \in \partial e$ に対して $\mathcal{B}_f'$ を定義すると、 $\mathcal{B}_f \subset \mathcal{B}_f' \subset \mathcal{A}_f$ および $\displaystyle \mathrm{cpx}(\mathcal{B}_f') \leq \mathrm{cpx}(\mathcal{B}_f)+1$ が成り立っている( $\mathcal{B}(E_f)$ は $E_f$ の生成する $V_J$ 上の $\sigma$ 加法族)。そうして、

$\displaystyle \mathbb{E}\left( \Bigl( \mathbf{1}_{E_e}-\mathbb{E}\Bigl(\mathbf{1}_{E_e} \ \Big| \ \bigvee_{f \in \partial e}\mathcal{B}_f'\Bigr) \Bigr) \prod_{f \in \partial e}\mathbf{1}_{E_f}\right) =0$

が成り立つ。理由: $F:=\prod_{f \in \partial e}\mathbf{1}_{E_f}$ は $\bigvee_{f \in \partial e}\mathcal{B}_f'$ -可測である。理由: $\mathbf{1}_{E_f}$ は $\mathcal{B}(E_f)$ -可測なので、 $\mathcal{B}_f'$ -可測、 $\bigvee_{f \in \partial e}\mathcal{B}_f'$ -可測となり、積をとった $F$ もそうである。また、Tao-§6(1)の基本性質(条件付き期待値の線形性と期待値保存)より、 $G:=\mathbf{1}_{E_e}-\mathbb{E}(\mathbf{1}_{E_e} \mid \bigvee_{f \in \partial e}\mathcal{B}_f')$ とおくと、 $\mathbb{E}(G \mid \bigvee_{f \in \partial e}\mathcal{B}_f')=0$ が成り立つ。よって、条件付き期待値作用素の自己随伴性より

$\langle F, G\rangle = \langle \mathbb{E}(F \mid \bigvee_{f \in \partial e}\mathcal{B}_f'), G\rangle = \langle F, \mathbb{E}(G \mid \bigvee_{f \in \partial e}\mathcal{B}_f')\rangle = 0$

を得る。従って、二つの式を差し引きすると

$\displaystyle \left|\mathbb{E}\left( \Bigl(\mathbb{E}\Bigl(\mathbf{1}_{E_e} \ \Big| \ \bigvee_{f \in \partial e}\mathcal{B}_f'\Bigr)-\mathbb{E}\Bigl(\mathbf{1}_{E_e} \ \Big| \ \bigvee_{f \in \partial e}\mathcal{B}_f\Bigr) \Bigr) \prod_{f \in \partial e}\mathbf{1}_{E_f}\right) \right| \geq \varepsilon$

が得られる。 $0 \leq \prod_{f \in \partial e}\mathbf{1}_{E_f} \leq 1$ なので、Cauchy-Schwarzの不等式より

$\displaystyle \mathbb{E}\left( \left|\mathbb{E}\Bigl(\mathbf{1}_{E_e} \ \Big| \ \bigvee_{f \in \partial e}\mathcal{B}_f'\Bigr)-\mathbb{E}\Bigl(\mathbf{1}_{E_e} \ \Big| \ \bigvee_{f \in \partial e}\mathcal{B}_f\Bigr)\right|^2\right) \geq \varepsilon^2$

となって、エネルギーギャップ公式より証明が完了する。 Q.E.D.

ランダムネスと構造のダイコトミー

$(d-1)$ 一様ハイパーグラフ $\partial H$ を $\displaystyle \partial H := \bigcup_{e \in H}\partial e$ と定義する。

補題２ $m, M, \varepsilon, \delta > 0$ とする。各 $e \in H$ に対して、 $\sigma$ 加法族 $\mathcal{B}_e \subset \mathcal{A}_e$ であって $\mathrm{cpx}(\mathcal{B}_e) \leq m$ を満たすものをとり、各 $f \in \partial H$ に対して、 $\sigma$ 加法族 $\mathcal{B}_f \subset \mathcal{A}_f$ であって $\mathrm{cpx}(\mathcal{B}_f) \leq M$ を満たすものをとる。このとき、次のいずれかが成立する:
(Randomness): 各 $f \in \partial H$ に対して $\mathcal{B}_f \subset \mathcal{B}_f' \subset \mathcal{A}_f$ なる $\sigma$ 加法族 $\mathcal{B}_f'$ が存在して、任意の $e \in H, E_e \in \mathcal{B}_e$ に対して

$\displaystyle \mathcal{E}_{E_e}\Bigl(\bigvee_{f \in \partial e}\mathcal{B}_f'\Bigr) < \mathcal{E}_{E_e}\Bigl(\bigvee_{f \in \partial e}\mathcal{B}_f\Bigr)+\varepsilon^2$ –①

および

$\displaystyle \Delta_e\Big( E_e \Big| \bigvee_{f \in \partial e}\mathcal{B}_f'\Bigr) \leq \delta$ –②

が成り立つ。
(Structure): 各 $f \in \partial H$ に対して $\mathcal{B}_f \subset \mathcal{B}_f' \subset \mathcal{A}_f$ なる $\sigma$ 加法族 $\mathcal{B}_f'$ が存在して、或る $e \in H, E_e \in \mathcal{B}_e$ に対して

$\displaystyle \mathcal{E}_{E_e}\Bigl(\bigvee_{f \in \partial e}\mathcal{B}_f'\Bigr) \geq \mathcal{E}_{E_e}\Bigl(\bigvee_{f \in \partial e}\mathcal{B}_f\Bigr)+\varepsilon^2$ –③

が成り立ち、任意の $f \in \partial H$ に対して

$\displaystyle \mathrm{cpx}(\mathcal{B}_f') \leq M+O_{\#J, m, \varepsilon, \delta}(1)$ −④

が成り立つ。

証明. 次のアルゴリズムを考える:
0. 初期化 $\mathcal{B}_f' := \mathcal{B}_f \ ({}^{\forall}f \in \partial H)$ . (①、④は成立している。)
1. if ②成立 then 停止
2. else 或る $e \in H$ および $E_e \in \mathcal{B}_e$ が存在して、

$\displaystyle \Delta_e\Bigl( E_d \Big| \bigvee_{f \in \partial e}\mathcal{B}_f' \Bigr) > \delta$

が成り立つ。よって、補題１より各 $f \in \partial e$ に対して $\mathcal{B}_f' \subset \mathcal{B}_f'' \subset \mathcal{A}_f$ なる $\sigma$ 加法族 $\mathcal{B}_f''$ が存在して $\mathrm{cpx}(\mathcal{B}_f'') \leq \mathrm{cpx}(\mathcal{B}_f')+1$ および

$\displaystyle \mathcal{E}_{E_e}\Bigl( \bigvee_{f \in \partial e}\mathcal{B}_f''\Bigr) \geq \mathcal{E}_{E_e}\Bigl( \bigvee_{f \in \partial e}\mathcal{B}_f'\Bigr) + \delta^2$

が成り立つ。

3. 代入 $\mathcal{B}_f' := \mathcal{B}_f'' \ ({}^{\forall}f \in \partial e)$ . ( $e$ は2. のもの。)
4. if ③成立 then 停止
5. else (①が成立) 1. へ

5. から2. へ移行する度に

$\displaystyle \sum_{e \in H}\sum_{E_e \in \mathcal{B}_e}\mathcal{E}_{E_e}\Bigl( \bigvee_{f \in \partial e}\mathcal{B}_f'\Bigr)$

は少なくとも $\delta^2$ 増加する。よって、 $n$ 回目の5. から2. への移行時

$\displaystyle \sum_{e \in H}\sum_{E_e \in \mathcal{B}_e}\mathcal{E}_{E_e}\Bigl( \bigvee_{f \in \partial e}\mathcal{B}_f'\Bigr) \geq \sum_{e \in H}\sum_{E_e \in \mathcal{B}_e}\mathcal{E}_{E_e}\Bigl( \bigvee_{f \in \partial e}\mathcal{B}_f\Bigr) + n\delta^2$

が成り立つ。一方、このとき①が成立しているため

$\begin{align} \sum_{e \in H}\sum_{E_e \in \mathcal{B}_e}\mathcal{E}_{E_e}\Bigl( \bigvee_{f \in \partial e}\mathcal{B}_f'\Bigr) &< \sum_{e \in H}\sum_{E_e \in \mathcal{B}_e}\mathcal{E}_{E_e}\Bigl( \bigvee_{f \in \partial e}\mathcal{B}_f\Bigr) +\sum_{e \in H}\sum_{E_e \in \mathcal{B}_e}\varepsilon^2 \\ &= \sum_{e \in H}\sum_{E_e \in \mathcal{B}_e}\mathcal{E}_{E_e}\Bigl( \bigvee_{f \in \partial e}\mathcal{B}_f\Bigr) + O_{\#J, m, \varepsilon}(1)\end{align}$

と評価できる( $\sigma$ 加法族の複雑度によるバウンドを使っている)。従って、1. で停止した場合はRandomnessが成立し、1. で停止せずに5. から2. への移行を繰り返すとしても、 $O_{\#J, m, \varepsilon, \delta}(1)$ 回目には必ず4. で停止する。このとき、Structureが成立している。 Q.E.D.

INTEGERS

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

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

Discrepancyとエネルギー

ランダムネスと構造のダイコトミー