インテジャーズ

INTEGERS

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

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

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

参考文献
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個しかないので、\deltaNには依存しないことに注意して、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

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

定義1 Jを有限集合とし、d \geq 0を整数とする。このとき、\binom{J}{d}
\displaystyle \binom{J}{d} := \{e \subset J \mid \#e = d\}
と定義する。\binom{J}{d}の部分集合Hのことを、d一様ハイパーグラフという。

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

定義2 ハイパーグラフ系とは4つ組V=(J, (V_j)_{j \in J}, d, H)であって、J: 有限集合、(V_j)_{j \in J}: 空でない有限集合の族、d \geq 1H \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

定義3 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_eV_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')

となって所望の漸近挙動に到達する。以下、最初に設けた仮定をはずす。G

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

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

\displaystyle \mathbb{E}_y :=  \left.\mathbb{E}\left(\prod_{j \in J}\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}\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として適用すると

\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)

が得られる。 Q.E.D.

*1:J=\{j\}のときは群準同型Z' \times Z \to Z'; \ (x,r) \mapsto x+\phi_j(r)が全射なので、群準同型性からZの各点でのファイバーの濃度は等しく、GT1,4の補題から

\displaystyle \mathbb{E}(\mathbf{1}_A(x+\phi_j(r) ) \mid x \in Z', r \in Z) = \mathbb{E}(\mathbf{1}_A(x) \mid x \in Z')
が成り立つ。これよりこの場合には主張が成り立つことがわかる。場合分けをする理由はハイパーグラフ系の定義でd \geq 1が必要であるから。

*2:i成分がr, j成分が-r, 残りが0であるような組を考えればよい。

*3:i成分が-rで残りが0であるような組を考える。