2018-01-09

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

この記事から複数記事用いて「ハイパーグラフ除去補題」の証明を行います。

参考文献
T. Tao, A variant of the hypergraph removal lemma, J. Combin. Theory Ser. A 113 (2006), 1257–1280.
T. Tao, The Gaussian primes contain arbitrarily shaped constellations, J. Anal. Math. 99 (2006), 109–176.

多次元版Szemerédiの定理

正整数 $N$ に対して、 $[-N, N]:=\{n \in \mathbb{Z} \mid -N \leq n \leq N\}$ とする。また、 $d$ を正整数として、集合 $A \subset \mathbb{Z}^d$ の上漸近密度 $\overline{d}(A)$ を

$\displaystyle \overline{d}(A) := \limsup_{N \to \infty}\frac{\#\{A \cap [-N, N]^d\}}{\#[-N, N]^d}$

で定義する。 $\mathbb{Z}^d$ 内の形状とは $\mathbb{Z}^d$ の相異なる点の有限族 $(v_j)_{j \in J}$ のことをいう。すなわち、 $J$ は有限集合で、 $v_j \in \mathbb{Z}^d$ である。形状が $(v_j)_{j \in J}$ である星座とは $a \in \mathbb{Z}^d, r \in \mathbb{Z}_{> 0}$ を用いて $(a+rv_j)_{j \in J}$ と表される有限族のことをいう。

多次元版Szemerédiの定理 (Furstenberg-Katznelson) $A \subset \mathbb{Z}^d$ を上漸近密度が正であるような集合とする。このとき、任意の $\mathbb{Z}^d$ 内の形状 $(v_j)_{j \in J}$ に対して、構成する点が全て $A$ の元であるような、形状が $(v_j)_{j \in J}$ である星座が無数に存在する。

これは一応今回の主役ではないが、副産物として証明される。

有限加法群に対するSzemerédiの定理

空でない有限集合 $Z$ と関数 $f\colon Z \to \mathbb{R}$ に対して、期待値を

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

と定義する。これまで同様ビッグオー記号やスモールオー記号を使用する。 $o_{x \to 0}(X)$ は絶対値が或る $c(x)X$ で押さえられて、 $\displaystyle \lim_{x \to 0}c(x)=0$ が成り立つ。 $c(x)$ の $x$ 以外の依存パラメータを $o_{x \to 0; y_1, \dots, y_m}$ のように添え字を付ける形で表す。 $\mathbf{1}_{\bullet}$ は特性関数。

有限加法群に対するSzemerédiの定理 $Z, Z'$ を有限加法群とし、 $(\phi_j)_{j \in J}$ を群準同型 $\phi_j\colon Z \to Z'$ の有限族とする。集合 $A \subset Z'$ が $0 < \delta < 1$ に対して

$\displaystyle \left.\mathbb{E}\left(\prod_{j \in J}\mathbf{1}_A(x+\phi_j(r) ) \ \right| \ x \in Z', r \in Z\right) \leq \delta$

を満たすならば、

$\displaystyle \mathbb{E}(\mathbf{1}_A(x) \mid x \in Z') = o_{\delta \to 0; \#J}(1)$

が成り立つ。

正整数 $N$ に対して、 $\mathbb{Z}_N := \mathbb{Z}/N\mathbb{Z}$ とする。

有限加法群に対する多次元Szemerédi $\Longrightarrow$ 多次元版Szemerédiの定理の証明. 任意の形状について、それを含むような(集合として)より大きな形状に対して多次元版Szemerédiの定理の主張を証明できればよい。よって、任意に整数 $M \geq 3$ をとって、 $[-M, M]^d$ の元達からなる形状に対して証明する。また、この形状は原点対称であるから、 $r$ としては零でないことを保証できればよい。 $\overline{d}(A) = \sigma > 0$ とすると、 $A(N):=A \cap [-N, N]^d$ とするとき $\#A(N) \geq \frac{\sigma}{2}\#[-N, N]^d$ が成り立つようないくらでも大きい整数 $N$ が存在する。そのような $N$ をとって固定し、 $N' := 6MN$ とする。 $Z:=\mathbb{Z}_{N'}, \ Z':=\mathbb{Z}_{N'}^d$ とする(これらは有限加法群である)。 $v \in [-M, M]^d$ に対して、群準同型写像 $\phi_v\colon Z \to Z'$ を $\phi_v(r'):=r'v$ と定める。 $\pi_{N'}$ で標準射影 $\mathbb{Z} \to \mathbb{Z}_{N'}$ および $\mathbb{Z}^d \to \mathbb{Z}_{N'}^d$ を表す $\iota := \left.\pi_{N'}\right|_{[-N, N]^d} \colon \mathbb{Z}^d \to \mathbb{Z}_{N'}^d$ は単射である。 $A':=\iota(A(N) ) \subset Z'$ とする。このとき、

$\displaystyle \mathbb{E}(\mathbf{1}_{A'}(x) \mid x \in Z') = \frac{\#A(N)}{\#Z'} \gg_{d, M} \sigma$

である。よって、有限加法群に対するSzemerédiの定理より、 $d, M, \sigma$ のみに依存する $\delta > 0$ が存在して

$\displaystyle \left.\mathbb{E}\left(\prod_{v \in [-M, M]^d}\mathbf{1}_{A'}(x+r'v) \ \right| \ x \in Z', r' \in Z\right) > \delta$

でなければならない。すなわち、任意の $v \in [-M, M]^d$ に対して $x+r'v \in A'$ となるような $(x, r') \in Z' \times Z$ が少なくとも $\delta (N')^{d+1}$ 個存在する。そのような $(x, r')$ のうち、 $r' \neq 0$ であるようなものをとる( $r'=0$ であるようなものは高々 $(N')^d$ 個しかないので、 $\delta$ は $N$ には依存しないことに注意して、 $N$ を十分大きくとれば $r' \neq 0$ であるようなものが存在しなくてはならないことがわかる)。 $0 \in [-M, M]^d$ なので、 $x \in A'$ であり、 $a:=\iota^{-1}(x) \in A(N)$ と定める。 $a \in [-N, N]^d$ である。次に、 $e_1:=(1, 0, \dots, 0) \in [-M, M]^d$ を考えて、 $r:=\mathrm{pr}_1(\iota^{-1}(x+r'e_1)-a) \in \mathbb{Z}$ と定める( $\mathrm{pr}_1$ は第一成分を取り出す射影)。このとき、 $r \in [-2N, 2N]$ である。第一成分を取り出すことと $\pi_{N'}$ をとることは可換であることから、 $\pi_{N'}(r) = r'$ である。従って、任意の $v \in [-M, M]^d$ に対して $\pi_{N'}(a+rv) = x+r'v$ が成り立つ。一方、 $\iota^{-1}(x+r'v) \in [-N, N]^d$ であることから、

$(a+rv)-\iota^{-1}(x+r'v) \in (-3MN, 3MN)^d$

が成り立つ。よって、 $N'$ の取り方から、任意の $v \in [-M, M]^d$ に対して $a+rv=\iota^{-1}(x+r'v') \in A(N)$ が示された。 $r'\neq 0$ であることから $r \neq 0$ である。 $N \to \infty$ とすることによって、所望の星座が無数に存在することもわかる。 Q.E.D.

ハイパーグラフ

グラフの辺は二頂点を結ぶものであるが、複数の頂点を連結させたハイパーエッジを考えたものをハイパーグラフという。

ハイパーグラフ - Wikipedia

ここでは、連結させる頂点の個数を一定にしたハイパーグラフのみを扱う。

定義１ $J$ を有限集合とし、 $d \geq 0$ を整数とする。このとき、 $\binom{J}{d}$ を

$\displaystyle \binom{J}{d} := \{e \subset J \mid \#e = d\}$

と定義する。 $\binom{J}{d}$ の部分集合 $H$ のことを、 $d$ 一様ハイパーグラフという。

$2$ 一様ハイパーグラフが通常のグラフである。

定義２ ハイパーグラフ系とは４つ組 $V=(J, (V_j)_{j \in J}, d, H)$ であって、 $J$ : 有限集合、 $(V_j)_{j \in J}$ : 空でない有限集合の族、 $d \geq 1$ 、 $H \subset \binom{J}{d}$ : $d$ 一様ハイパーグラフであるようなものをいう。 $e \subset J$ に対して、 $\displaystyle V_e:=\prod_{j \in e}V_j$ と定義し、標準射影を $\pi_e\colon V_J \twoheadrightarrow V_e$ とする。 $e \subset J$ に対して、 $V_J$ 上の $\sigma$ 加法族 $\mathcal{A}_e$ を $\displaystyle \mathcal{A}_e := \{\pi_e^{-1}(E) \mid E \subset V_e\}$ で定義する。

有限集合上の $\sigma$ 加法族に関する基礎知識は仮定する( $\mathbb{Z}_N$ で記述していたが、有限集合上の $\sigma$ 加法族に関する一般論を展開しているため、 $V_J$ としても同様のことが成り立つ): タオのセメレディ論文の§6を読む (その一) - INTEGERS

定義３ $V=(J, (V_j)_{j \in J}, d, H)$ をハイパーグラフ系として、 $\mathcal{B}$ を $V_J$ 上の $\sigma$ 加法族とする。このとき、 $\mathcal{B}$ の複雑度 $\mathrm{cpx}(\mathcal{B})$ を、 $\mathcal{B}$ を $\sigma$ 加法族として生成する集合の個数の最小値と定める。

定義から明らかに

$\mathrm{cpx}(\mathcal{B}_1 \vee \mathcal{B}_2) \leq \mathrm{cpx}(\mathcal{B}_1)+\mathrm{cpx}(\mathcal{B}_2)$

が成り立つ( $\vee$ は $\sigma$ 加法族の合併)。 $\mathcal{B}$ のアトム全体のなす集合を $\mathrm{Atom}(\mathcal{B})$ で表すと、

$\displaystyle \#\mathcal{B} \leq 2^{\#\mathrm{Atom}(\mathcal{B})} \leq 2^{2^{\mathrm{cpx}(\mathcal{B})}}$

なる評価ができることがわかる。

ハイパーグラフ除去補題

次が今回の主定理：

定理 (ハイパーグラフ除去補題) $V=(J, (V_j)_{j \in J}, d, H)$ をハイパーグラフ系とする。ハイパーエッジ $e \in H$ 毎に $E_e \in \mathcal{A}_e$ であって、 $0 < \delta < 1$ に対して

$\displaystyle \left.\mathbb{E}\left(\prod_{e \in H}\mathbf{1}_{E_e}(x) \ \right| \ x \in V_J\right) \leq \delta$

が成り立つようなものをとる。このとき、各 $e \in H$ に対して或る $E_e' \in \mathcal{A}_e$ が存在して

$\displaystyle \bigcap_{e \in H}E_e' = \emptyset,$

$\displaystyle \mathbb{E}\left(\mathbf{1}_{E_e \setminus E_e'}(x) \mid x \in V_J\right) = 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'}$

が成り立つ。

$\sigma$ 加法族の複雑度の評価から、 $\#\mathcal{B}_{e'} = O_{\delta, \#J}(1)$ が成り立つことに注意。

ハイパーグラフ除去補題 $\Longrightarrow$ 有限加法群に対するSzemerédiの定理の証明. 最初に $Z'$ が

$\displaystyle \{\phi_i(r)-\phi_j(r) \mid i, j \in J, r \in Z\}$

で生成されている場合に証明する。

$\displaystyle \left.\mathbb{E}\left(\prod_{j \in J}\mathbf{1}_A(x+\phi_j(r) ) \ \right| \ x \in Z', r \in Z\right) \leq \delta$

を仮定する。 $\#J \geq 2$ としてよい*1。このとき、ハイパーグラフ系 $V=(J, (V_j)_{j \in J}, d, H)$ を $V_j = Z \ ({}^{\forall}j \in J)$ , $d=\#J-1$ , $H=\binom{J}{d}$ と定める。 $e = J \setminus \{j\} \in H$ に対して $E_e \subset V_J=Z^J$ を

$\displaystyle E_e:=\left\{(x_i)_{i \in J} \in Z^J \ \left| \ \sum_{i \in J}\left(\phi_i(x_i)-\phi_j(x_i)\right) \in A\right\}\right.$

と定義する。 $\sum_{i \in J}\left(\phi_i(x_i)-\phi_j(x_i)\right)$ は $x_j$ に依存しないため、 $E_e \in \mathcal{A}_e$ であることがわかる。群準同型 $\Phi \colon V_J \to Z' \times Z$ を

$\displaystyle \Phi ( (x_i)_{i \in J}) := \left(\sum_{i \in J}\phi_i(x_i), -\sum_{i \in J}x_i\right)$

と定める。このとき、

$\displaystyle \bigcap_{e \in H}E_e = \Phi^{-1}\left(\{(x, r) \in Z'\times Z \mid x+\phi_j(r) \in A, \ {}^{\forall}j \in J\}\right)$ −①

が成り立つ。 $\Phi$ は全射である。理由: $\mathrm{Im}(\Phi)$ は任意の $i, j \in J, r \in Z$ に対して $(\phi_i(r)-\phi_j(r), 0)$ を含む*2。よって、最初に設けた仮定より $Z'\times \{0\} \subset \mathrm{Im}(\Phi)$ がわかる。また、任意の $j \in J, r \in Z$ に対して $(-\phi_j(r), r) \in \mathrm{Im}(\Phi)$ でもある*3。すると、任意の $(x, r) \in Z' \times Z$ に対して、 $\Phi(\mathbf{x}_j)=(x+\phi_j(r), 0)$ , $\Phi(\mathbf{y}_j) = (-\phi_j(r), r)$ となるような $\mathbf{x}_j, \mathbf{y}_j$ を取れば( $j$ は何でもよい)、 $\Phi(\mathbf{x}_j+\mathbf{y}_j) = (x, r)$ となる。

よって、 $\Phi$ は群準同型であることから $Z'$ の $Z'\times Z$ による一様被覆なのでGT1,4の補題を適用でき、

$\displaystyle \mathbf{x} \in \Phi^{-1}\left(\{(x, r) \in Z'\times Z \mid x+\phi_j(r) \in A, \ {}^{\forall}j \in J\}\right) \Longleftrightarrow \prod_{j \in J}\mathbf{1}_A(x+\phi_j(r) ) = 1 \ (\Phi(\mathbf{x}) = (x, r) )$

であることから①と仮定より

$\displaystyle \left.\mathbb{E}\left(\prod_{e \in H}\mathbf{1}_{E_e}(\mathbf{x}) \ \right| \ \mathbf{x} \in V_J\right) = \left.\mathbb{E}\left(\prod_{j \in J}\mathbf{1}_A(x+\phi_j(r) ) \ \right| \ x \in Z', r \in Z\right) \leq \delta$

を得る。よって、ハイパーグラフ除去補題より $e \in H$ 毎に $E_e' \in \mathcal{A}_e$ が存在して、

$\displaystyle \bigcap_{e \in H}E_e' = \emptyset$ −②

および

$\displaystyle \#(E_e \setminus E_e') = o_{\delta \to 0; \#J}(\#V_J) \quad ({}^{\forall}e \in H)$

が成り立つ(後半は期待値の定義よりわかる)。なお、多次元Szemerédiの導出には $\sigma$ 加法族の複雑度に関する主張は不要である。①より

$\displaystyle \Phi^{-1}(A \times \{0\}) \subset \bigcap_{e \in H}E_e$

なので、これと②より

$\displaystyle \Phi^{-1}(A \times \{0\}) \subset \bigcup_{e \in H}(E_e \setminus E_e')$

が成り立つ。よって、或る $e = J\setminus \{j\}$ が存在して

$\displaystyle \#\{(E_e\setminus E_e') \cap \Phi^{-1}(A \times \{0\})\} \geq \frac{\#\Phi^{-1}(A \times \{0\})}{\#J}$ −③

となる(以下、固定)。理由: そのような $e$ が存在しなかったと仮定すると、 $\#H = \#J$ に注意して

$\begin{align}\#\Phi^{-1}(A \times \{0\}) &= \#\left\{\bigcup_{e \in H}(E_e \setminus E_e') \cap \Phi^{-1}(A \times \{0\})\right\} \\ &\leq \sum_{e \in H} \#\{(E_e\setminus E_e') \cap \Phi^{-1}(A \times \{0\})\} < \#H\cdot \frac{\#\Phi^{-1}(A \times \{0\})}{\#J} = \#\Phi^{-1}(A \times \{0\})\end{align}$

となって矛盾する。

$\Phi^{-1}(A \times \{0\})$ は超平面 $\{(x_i)_{i \in J} \mid \sum_{i \in J}x_i=0\}$ に含まれているので、 $\pi_e\colon V_J \to V_e$ は $V_e$ の各点で $\#Z$ 重になっているが、制限写像 $\left.\pi_e\right|_{\Phi^{-1}(A\times \{0\})}$ は単射となる。よって、 $E_e\setminus E_e' \in \mathcal{A}_e$ に注意して、

$\displaystyle \#\{(E_e\setminus E_e') \cap \Phi^{-1}(A\times \{0\})\} \leq \frac{\#(E_e\setminus E_e')}{\#Z} = o_{\delta \to 0; \#J}(\#V_J/\#Z)$ −④

が成り立つ。 $\Phi$ の全射性から

$\displaystyle \frac{\#\Phi^{-1}(A \times \{0\})}{\#V_J} = \frac{\#A}{\#(Z'\times Z)} = \frac{\#A}{\#Z\cdot \#Z'}$

である。③と④を合わせると

$\displaystyle \#A = \#Z\cdot \#Z' \cdot \frac{\#\Phi^{-1}(A\times \{0\})}{\#V_J} \leq \#Z\cdot \#Z' \cdot \frac{\#J\cdot \#\{(E_e\setminus E_e') \cap \Phi^{-1}(A\times \{0\})\}}{\#V_J} \leq o_{\delta \to 0; \#J}(\#Z')$

となって所望の漸近挙動に到達する。以下、最初に設けた仮定をはずす。 $J^{\ast}:=J\sqcup \{\bullet\}$ とし、 $\phi_{\bullet}\colon Z \to Z'$ をゼロ写像とする。 $G$ を

$\displaystyle \{\phi_i(r)-\phi_j(r) \mid i, j \in J^{\ast}, r \in Z\}$

が生成する $Z'$ の部分群とする。 $Z'/G$ の代表系 $\mathcal{R}$ を一つとる。 $y \in \mathcal{R}$ に対して

$\displaystyle \mathbb{E}_y := \left.\mathbb{E}\left(\prod_{j \in J^{\ast}}\mathbf{1}_A(x+\phi_j(r) ) \ \right| \ x \in y+G, r \in Z\right)$

とすると、

$\displaystyle \mathbb{E}(\mathbb{E}_y \mid y \in \mathcal{R}) = \left.\mathbb{E}\left(\prod_{j \in J^{\ast}}\mathbf{1}_A(x+\phi_j(r) ) \ \right| \ x \in Z', r \in Z\right) \leq \left.\mathbb{E}\left(\prod_{j \in J}\mathbf{1}_A(x+\phi_j(r) ) \ \right| \ x \in Z', r \in Z\right) \leq \delta$

となる。これより、高々 $O(\sqrt{\delta}\#Z'/\#G)$ 個の例外を除く $y \in \mathcal{R}$ に対して $\mathbb{E}_y \leq \sqrt{\delta}$ が成り立つ。理由: $\mathbb{E}_y > \sqrt{\delta}$ が成り立つような $y \in \mathcal{R}$ の個数が $\sqrt{\delta}\#Z'/\#G$ より大きかったとする。すると、

$\displaystyle \mathbb{E}(\mathbb{E}_y \mid y \in \mathcal{R}) \geq \frac{\#G}{\#Z'}\sum_{\substack{y \in \mathcal{R} \\ \mathbb{E}_y > \sqrt{\delta}}}\mathbb{E}_y > \frac{\#G}{\#Z'}\cdot \frac{\sqrt{\delta}\#Z'}{\#G} \cdot \sqrt{\delta} = \delta$

となって矛盾する。 $\mathbb{E}_y \leq \sqrt{\delta}$ なる $y$ について、最初のケースを $Z' \mapsto G$ , $A \mapsto (A-y) \cap G$ として適用すると( $J^{\ast}$ を考えたことによって $\phi_j$ の像が $G$ となって適用可能であることが分かる)

$\displaystyle \#\{A \cap (y+G)\} = \#\{(A-y) \cap G\} = o_{\sqrt{\delta} \to 0; \#J}(\#G)$

が得られる。よって、

$\displaystyle \#A \leq o_{\sqrt{\delta} \to 0; \#J}(\#G) \cdot \frac{\#Z'}{\#G} + \#G\cdot O\left(\frac{\sqrt{\delta}\#Z'}{\#G}\right) = o_{\delta \to 0; \#J}(\#Z')$

となって証明が完了する。 Q.E.D.

重み付きハイパーグラフ除去補題

ハイパーグラフ除去補題を重みつきにバージョアップさせる(これを後々使いたい)。

定理 (重み付きハイパーグラフ除去補題) $V=(J, (V_j)_{j \in J}, d, H)$ をハイパーグラフ系とする。ハイパーエッジ $e \in H$ 毎に関数 $f_e\colon V_e \to [0, 1]$ であって、 $0 < \delta < 1$ に対して

$\displaystyle \left.\mathbb{E}\left(\prod_{e \in H}f_e(\pi_e(x) ) \ \right| \ x \in V_J\right) \leq \delta$

が成り立つようなものをとる。このとき、各 $e \in H$ に対して或る $E_e' \in \mathcal{A}_e$ が存在して

$\displaystyle \bigcap_{e \in H}E_e' = \emptyset,$

$\displaystyle \mathbb{E}\left(f_e(\pi_e(x) )\mathbf{1}_{V_J \setminus E_e'}(x) \mid x \in V_J\right) = o_{\delta \to 0; \#J}(1)$

が成り立つ。更に、 $e' \subset J, \ \#e' < d$ に対して部分 $\sigma$ 加法族 $\mathcal{B}_{e'} \subset \mathcal{A}_{e'}$ が存在して,

$\#\mathcal{B}_{e'} = O_{\delta, \#J}(1)$

かつ任意の $e \in H$ に対して

$\displaystyle E_e' \in \bigvee_{e' \subsetneq e}\mathcal{B}_{e'}$

が成り立つ。

$E_e \in \mathcal{A}_e$ に対して、 $E_e=\pi_e^{-1}(\overline{E}_e)$ となるような $\overline{E}_e \subset V_J$ をとって $f_e:=\mathbf{1}_{\overline{E}_e}$ とする。このとき、 $f_e\circ \pi_e = \mathbf{1}_{E_e}$ , $\mathbf{1}_{E_e}\mathbf{1}_{V_J\setminus E_e'} = \mathbf{1}_{E_e \setminus E_e'}$ が成り立つのでハイパーグラフ除去補題になる。

証明. $e \in H$ に対して、

$\displaystyle E_e := \{x \in V_J \mid f_e(\pi_e(x) ) \geq \delta^{\frac{1}{2\#H}}\}$

と $E_e$ を定義すると、 $\pi_e$ を合成していることから $E_e \in \mathcal{A}_e$ である。今、

$\displaystyle \left.\mathbb{E}\left(\prod_{e \in H}f_e(\pi_e(x) ) \ \right| \ x \in V_J\right) \leq \delta$

と仮定していることから、

$\displaystyle \left.\mathbb{E}\left(\prod_{e \in H}\mathbf{1}_{E_e}(x) \ \right| \ x \in V_J\right) \leq \sqrt{\delta}$

が得られる。理由: $\displaystyle x \in \bigcap_{e \in H}E_e$ であれば $\displaystyle \prod_{e \in H}f_e(\pi_e(x) )\geq \sqrt{\delta}$ が成り立つので、

$\displaystyle \#\bigcap_{e \in H}E_e > \sqrt{\delta}\#V_J$

と仮定すると

$\displaystyle \sum_{x \in V_J}\prod_{e \in H}f_e(\pi_e(x) ) > \sqrt{\delta}\#V_J \times \sqrt{\delta} = \delta \#V_J$

となって矛盾する。従って、ハイパーグラフ除去補題によって複雑度の条件等適切な性質を満たす $E_e' \in \mathcal{A}_e$ 達が存在して

$\displaystyle \mathbb{E}\left(\mathbf{1}_{E_e}(x)\mathbf{1}_{V_J\setminus E_e'}(x) \mid x \in V_J \right) = o_{\delta \to 0; \#J}(1)$

が成り立つ。 $x \in V_J$ 毎に

$\displaystyle f_e(\pi_e(x) ) \leq \mathbf{1}_{E_e}(x) + \delta^{\frac{1}{2\#H}}$

が成り立つので

$\displaystyle \mathbb{E}\left(f_e(\pi_e(x) )\mathbf{1}_{V_J \setminus E_e'}(x) \mid x \in V_J\right) \leq \mathbb{E}\left(\mathbf{1}_{E_e}(x)\mathbf{1}_{V_J\setminus E_e'}(x) \mid x \in V_J \right) + \delta^{\frac{1}{2\#H}} = o_{\delta \to 0; \#J}(1)$