グリーン・タオの定理3 三角形除去補題の利用
こんにちは,itouです.今回はグリーン・タオの定理シリーズ第3回,
三角形除去補題
$\Rightarrow$アイタイ・セメレディの定理(コーナー定理ともいう)
$\Rightarrow$ロスの定理
の流れを見ていきます.
各命題の主張は以下の通り.
任意の$\varepsilon >0$に対して$\delta=\delta_{\triangle}(\varepsilon)$が存在して,以下が成立する.グラフ$G$を任意に考えて,その頂点の個数を$n$とおく.もし$G$が高々$\delta n^3$個しか三角形を含まなければ,高々$\varepsilon n^2$個の辺を除去することによって,三角形を含まないような$G$の部分グラフを得ることができる.
整数$a,b,c$(ただし$c\ne0$)を用いて$\{(a,b),(a+c,b),(a,b+c)\}$と表される$\mathbb Z^2$の部分集合をコーナーとよぶ.実数$0<\delta \leq 1$に対して正整数$N_{AS}(\delta)$が存在して,以下が成立する.$N\geq N_{AS}(\delta)$を満たす任意の整数$N$に対して,$\sharp A\geq \delta N^2$であるような集合$A\subset [N]^2$はコーナーを含む.
実数$0<\delta \leq 1$に対して正整数$N_{Roth}(\delta)$が存在して,以下が成立する.$N\geq N_{Roth}(\delta)$を満たす任意の整数$N$に対して,$\sharp A \geq \delta N$であるような集合$A\subset [N]$は長さ3の等差数列を含む.
(正確には後述するように三角形除去補題をグラフの言葉で書いた定理を使う)
ここからはグラフ理論の話です.
まず定義を並べます.
定義
頂点の集合$V$,辺の集合$E$の組$G=(V,E)$のことをグラフという.
以降グラフといえば単純無向有限グラフ(辺としてループと多重辺をもたず辺に向きがない,頂点の数が有限のグラフ)を考えます.そうすると辺はその両端の頂点からなる2元集合と同一視できます.つまり$E\subset \{e\in \mathfrak P(V):\sharp e =2\}$と考えてよいです.
※$\mathfrak P(V)$は$V$の冪集合
これを一般化して,
グラフの定義において辺集合を$E\subset \mathfrak P(V)\backslash \{\varnothing\}$と同一視したものをハイパーグラフという.
つまり辺とは頂点たちの関係のことをいいます.このように集合に構造を与えていくのが本書におけるグラフの役割です.
集合${V \choose r}$を${V \choose r}=\{e\in \mathfrak P (V):\sharp e=r\}$とする.
$V$($\sharp V=k$)を有限集合とし,$r$を正整数とする.このとき,$V$と${V \choose r}$の部分集合$E\subset {V \choose r}$の組$(V,E)$のことを($k$頂点)$r$グラフという.
※本には単に$r$グラフと書かれていますが,わかりやすくするために($k$頂点)$r$グラフとかくことがあります.
※($k$頂点)$r$グラフは$r$一様ハイパーグラフともいいます.
辺集合$E$は${V \choose r}$の部分集合だということです.(これは大事)
2つの$r$グラフ$G=(V,E),G'=(V',E')$について,$V\subset V'$かつ$E\subset E'$であるとき,$G$は$G'$の部分$r$グラフであるという.また全単射写像$f:V\rightarrow V’$であって「$e\in E\Leftrightarrow f(e)\in E'$」が成り立つとき,$G$と$G'$は同型であるという.
これは大丈夫だと思います.
$k,r$を$r\in [k]$を満たす正整数とする. $k$頂点完全$r$グラフ$K^{(r)}_k= (V,E)$を$V=[k]$,$E={[k] \choose r }$によって定める.また,$K^{(2)}_k=K_k$と略記する.$K_k$を$k$頂点完全グラフという.
$[N]$とは1以上$N$以下の整数の集合でした.$k$頂点完全グラフは
辺集合$E$が${[k] \choose r }$に等しいような(k頂点)$r$グラフをいいます.
$V_1,V_2,V_3$が有限集合であり,各$e \in {[3] \choose 2}=\{\{1,2\},\{2,3\},\{3,1\}\}$に対して$ E_e\subset V_1\times V_2\times V_3$であるとき,$D=((V_1,V_2,V_3);E_{\{1,2\}},E_{\{2,3\}},E_{\{3,1\}})$を3部2グラフデータという.また,これを$D=(V_1,V_2,V_3;E_{12},E_{23},E_{31})$と略記する.
次節のイメージも参考にしてください.
「頂点集合が3個の部分に分けられていて,同じ部分に属する相異なる頂点たちが同じ辺の構成要素になることがないような2グラフ」のことを3部2グラフという.3部2グラフデータ$D=(V_1,V_2,V_3;E_{12},E_{23},E_{31})$が与えられたとき,$V=\bigsqcup_{j\in [3]}V_j$とおき,$E=\bigsqcup_{e\in {[3] \choose 2}}E_e$を自然に${V \choose 2}$の部分集合と思うことによって,3部2グラフを自然に構成できる.このとき,$G$を$D$から構成される3部2グラフとよぶ.
$\bigsqcup_{i\in A_i}=\bigcup_{i\in I}\{(a,i):\in A_i \}$です.(これを非交和といいます.)
グラフ$G$に対して,$K_3$と同型な$G$の部分グラフのことを$G$に含まれる三角形という.
$K_3(D)$を3部2グラフデータ$D$から構成される3部2グラフに含まれる三角形の頂点集合の集まりとする.すなわち,
\begin{align}
K_3(D)=\{(v_1,v_2,v_3)\in V_1\times V_2\times V_3\}:(v_1,v_2)\in E_{12},(v_2,v_3)\in E_{23} ,(v_3,v_1)\in E_{31}
\end{align}
と定義する.
グラフとは頂点集合と,頂点間の関係(辺)から成り立っています.そのような集合と関係のセットのルールこそがグラフなのです.頂点集合はなんでもよいです.すぐ後には格子点の無限集合を頂点としてもつグラフが登場します.
イメージ
3部2グラフのことを単に3部グラフともいいます.3部グラフとは下の図のような構造をもつグラフです.
3部グラフのイメージ
三角形除去補題
さて,三角形除去補題とは以下の命題でした.
任意の$\varepsilon >0$に対して$\delta=\delta_{\triangle}(\varepsilon)$が存在して,以下が成立する.グラフ$G$を任意に考えて,その頂点の個数を$n$とおく.もし$G$が高々$\delta n^3$個しか三角形を含まなければ,高々$\varepsilon n^2$個の辺を除去することによって,三角形を含まないような$G$の部分グラフを得ることができる.
対偶をとってみると主張は
$G$において,高々$\varepsilon n^2$個の辺を除去するだけでは三角形をなくすことが決してできないならば,$G$は高々$\delta n^3$個よりも多くの三角形を含む
です.
ざっくり説明すると「三角形が少ないグラフは三角形を一切なくすことができる」
となります.
この補題をグラフの言葉で述べると以下のようになります.
任意の$\varepsilon >0$に対して$\delta=\delta_{TRL}(\varepsilon)>0$が存在して,以下が成立する.3部グラフデータ$D=(V_1,V_2,V_3;E_{12},E_{23},E_{31})$が
\begin{align}
\sharp K_3(D)\leq\delta \cdot\sharp V_1 \cdot\sharp V_2\cdot \sharp V_3
\end{align}
を満たすとき,3部グラフデータ$ D'=(V_1,V_2,V_3;E'_{12},E'_{23},E'_{31})$が存在して$K_3(D')=\varnothing$かつ任意の$(i,j)\in \{(1,2),(2,3),(3,1)\}$に対して
\begin{align}
\sharp(E_{ij}\backslash E'_{ij})\leq \varepsilon・\sharp V_i・\sharp V_j
\end{align}
が成り立つ.
$\sharp(E_{ij}\backslash E'_{ij})$は除去すべき三角形の個数のことで,それが任意の$\varepsilon$で上から抑えられるということです.たしかに先の三角形除去補題と同じことを言っていますね.
3部グラフ版三角形除去補題においては三角形を除去したグラフ$G'$が$G$の部分グラフでなくてもよいという意味で,上の三角形除去補題よりも3部グラフ版三角形除去補題の方が強い定理です.今後単に三角形除去補題というときは3部グラフ版三角形除去補題を指すことにします.
三角形除去補題$\Rightarrow$アイタイ・セメレディの定理
実数$\delta$を任意にとって,$N_{AS}=\lceil \frac{1}{2}(\frac{1}{\delta_{TRL}(\delta /5)}+1) \rceil$と定義します.$N \geq N_{AS}$とし,$\sharp A \geq\delta N^2$を満たす集合$A\subset [N]^2$をとります.この$A$に対し,3部グラフデータ$D=(V_1,V_2,V_3;E_{12},E_{23},E_{31})$を以下のように定めます.この$A$に対し,
頂点集合は
\begin{align}
V_1&=\{L_1(a):a\in [N]\} \\
V_2&=\{L_2(a):a\in [N]\} \\
V_3&=\{L_3(a):a\in [N]\} \\
\end{align}
とします.ただし,
\begin{align}
L_1(a)&=\{(x,y)\in \mathbb Z^2:x=a\} \\
L_2(a)&=\{(x,y)\in \mathbb Z^2:y=a\} \\
L_3(a)&=\{(x,y)\in \mathbb Z^2:x+y=a\} \\
\end{align}
とします.$L_i(a)$は直線上の格子点の集合ですが,単に直線と呼ぶことにします.その直線ひとつひとつを頂点とします.
辺集合を次のように定めます.
\begin{align} (L_i,L_j)\in E_{ij}\Leftrightarrow \text{2直線$L_i,L_j$の交点が$A$の元} \end{align}
いま,$K_3(D)=K_3(D)^{\triangle}\cup K_3(D)^{\bullet}$と分割できます.ただし,
$K_3(D)^{\triangle} $とは,
「三角形の頂点をなす3直線のうち,2直線を選んでその交点として得られる3つの格子点が$A$内のコーナーとなるような三角形の集合」で,
$K_3(D)^{\bullet}$とは,
「三角形の頂点をなす3直線の交点が$A$の1元集合であるような三角形の集合」
です.それぞれ非自明なコーナー,自明なコーナーに対応した三角形です.言いたいのは$K_3(D)^{\triangle}\ne \varnothing $でした.背理法で示します.
$K_3(D)^{\triangle}= \varnothing $を仮定すると,
\begin{align}
&\sharp K_3(D)
=K_3(D)^{\bullet}=\sharp A \leq N^2\leq\delta_{TRL}(\frac{\delta }{5})\cdot\sharp V_1 \cdot\sharp V_2\cdot\sharp V_3
\end{align}
です.ただし最後の不等号は$N_{AS}$の定義と$ N \geq N_{AS}$を用いました.さて,これは三角形除去補題の仮定であったので,3部グラフデータ$ D'=(V_1,V_2,V_3;E'_{12},E'_{23},E'_{31})$が存在して$K_3(D')=\varnothing$かつ任意の$(i,j)\in \{(1,2),(2,3),(3,1)\}$に対して
\begin{align}
\sharp(E_{ij}\backslash E'_{ij})\leq \varepsilon・\sharp V_i・\sharp V_j
\end{align}
です.各$E_{ij}\backslash E'_{ij}$に属する辺を除去するとき,$K_3(D)^{\bullet}$に属する三角形すべてから辺を一つずつ除去しなければなりません.これら$K_3(D)^{\bullet}$に属する三角形は2つの頂点(=2直線)から残りの1点が決まるので,どの2つも辺を共有することはあり得ません.(1辺を共有するならば同じ三角形なので)よって,除去すべき辺の個数は少なくとも$K_3(D)^{\bullet}$の元以上であり,
\begin{align}
K_3(D)^{\bullet}\leq \sum_{i,j\in (1,2),(2,3)(3,1)}\sharp(E_{ij}\backslash E'_{ij})\leq\frac{\delta}{5}(5N^2-2N)<\delta N^2
\end{align}
が成り立ちます.最後から2番目の不等号は$\sharp V_1=N,\sharp V_2=N,\sharp V_3=2N-1$に注意し,$N\cdot N+N\cdot (2N-1)+(2N-1)\cdot N=5N^2-2N$より分かります.
$K_3(D)^{\bullet}=\sharp A$だったので,結局$ \sharp A<\delta N^2$を得ますが,これは$ \sharp A\geq\delta N^2$に矛盾し,証明が完了します.
アイタイ・セメレディの定理$\Rightarrow$ロスの定理
実数$0<\delta\leq 1$を任意にとって,$N_{Roth}=\max\{N_{AS}(\delta^2/5),\lceil 26/\delta \rceil\}$とする.$N\geq N_{Roth}(\delta)$とし,$\sharp A\geq\delta N$を満たす$A\subset [N]$をとります.集合$B\subset [N]^2$を
\begin{align}
B=\{(x,y)\in [N]^2 :x+2y \in A\}
\end{align}
とします.
$x+2y=a$なる$(x,y)\in[N]^2$は$\lfloor \frac{a-1}{2} \rfloor$個あるので,
\begin{align}
&\sharp B\geq \sum_{a\in [\lceil \delta N \rceil]} \lfloor \frac{a-1}{2} \rfloor>\sum_{a\in [\lceil \delta N \rceil]}\frac{a-3}{2}\\
&=\frac{1}{2}\cdot\frac{\lceil \delta N \rceil(\lceil \delta N \rceil+1)}{2}-\frac{3}{2}\lceil \delta N \rceil\\
&>\frac{\delta^2N^2}{4}-\frac{5\delta N}{4}-\frac{5}{4}\geq\frac{\delta^2N^2}{5}
\end{align}
よって,アイタイ・セメレディの定理より,$B$はコーナー$\{(a,b),(a+c,b),(a,b+c)\}$を含みます.$(a,b\in \mathbb Z_{>0},c\in\mathbb Z\backslash\{0\})$.このとき,$B$の定義より$A$は$\{a+2b,a+2b+c,a+2b+2c\}$を含むことが分かります.これは長さ3の等差数列.
感想
三角形除去補題$\Rightarrow$アイタイ・セメレディの定理の証明におけるグラフの作り方は見事ですね.次回はこれの一般化の証明を追っていきます.
謝辞
ここまで読んで下さりありがとうございました。誤植等指摘お願いいたします.
この記事を高評価した人
この記事に送られたバッジ
投稿者
