グリーン・タオの定理3　三角形除去補題の利用

こんにちは,itouです.今回はグリーン・タオの定理シリーズ第3回,

の流れを見ていきます.
各命題の主張は以下の通り.

(正確には後述するように三角形除去補題をグラフの言葉で書いた定理を使う)

ここからはグラフ理論の話です.
まず定義を並べます.

定義

以降グラフといえば単純無向有限グラフ(辺としてループと多重辺をもたず辺に向きがない,頂点の数が有限のグラフ)を考えます.そうすると辺はその両端の頂点からなる2元集合と同一視できます.つまり$E\subset \{e\in \mathfrak{P}(V):\mathrm{♯}e=2\}$と考えてよいです.
※$\mathfrak{P}(V)$は$V$の冪集合
これを一般化して,

つまり辺とは頂点たちの関係のことをいいます.このように集合に構造を与えていくのが本書におけるグラフの役割です.

※本には単に$r$グラフと書かれていますが,わかりやすくするために($k$頂点)$r$グラフとかくことがあります.
※($k$頂点)$r$グラフは$r$一様ハイパーグラフともいいます.
辺集合$E$は$(\genfrac{}{}{0ex}{}{V}{r})$の部分集合だということです.(これは大事)

これは大丈夫だと思います.

$[N]$とは1以上$N$以下の整数の集合でした.$k$頂点完全グラフは
辺集合$E$が$(\genfrac{}{}{0ex}{}{[k]}{r})$に等しいような(k頂点)$r$グラフをいいます.

次節のイメージも参考にしてください.

$\underset{i\in I}{⨆}{A}_i=\bigcup _{i\in I}\{(a,i):a\in A_i\}$です.(これを非交和といいます.)

グラフとは頂点集合と,頂点間の関係(辺)から成り立っています.そのような集合と関係のセットのルールこそがグラフなのです.頂点集合はなんでもよいです.すぐ後には格子点の無限集合を頂点としてもつグラフが登場します.

イメージ

3部2グラフのことを単に3部グラフともいいます.3部グラフとは下の図のような構造をもつグラフです.
3部グラフのイメージ

三角形除去補題

さて,三角形除去補題とは以下の命題でした.

対偶をとってみると主張は

です.

ざっくり説明すると「三角形が少ないグラフは三角形を一切なくすことができる」
となります.

この補題をグラフの言葉で述べると以下のようになります.

$\mathrm{♯}(E_{ij}\mathrm{\setminus }{E}_{ij}^{\prime })$は除去すべき三角形の個数のことで,それが任意の$\epsilon$で上から抑えられるということです.たしかに先の三角形除去補題と同じことを言っていますね.

3部グラフ版三角形除去補題においては三角形を除去したグラフ$G^{\prime }$が$G$の部分グラフでなくてもよいという意味で,上の三角形除去補題よりも3部グラフ版三角形除去補題の方が強い定理です.今後単に三角形除去補題というときは3部グラフ版三角形除去補題を指すことにします.

三角形除去補題$\Rightarrow$アイタイ・セメレディの定理

実数$\delta$を任意にとって,$N_{AS}=\lceil \frac{1}{2}(\frac{1}{{\delta }_{TRL}(\delta /5)}+1)\rceil$と定義します.$N\ge N_{AS}$とし,$\mathrm{♯}A\ge \delta N^2$を満たす集合$A\subset [N{]}^2$をとります.この$A$に対し,3部グラフデータ$D=(V_1,V_2,V_3;E_{12},E_{23},E_{31})$を以下のように定めます.この$A$に対し,
頂点集合は

$$\begin{array}{rl}{V}_1& =\{L_1(a):a\in [N]\}\\ V_2& =\{L_2(a):a\in [N]\}\\ V_3& =\{L_3(a):a\in [2,2N]\}\end{array}$$
とします.ただし,
$$\begin{array}{rl}{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{array}$$

とします.$L_i(a)$は直線上の格子点の集合ですが,単に直線と呼ぶことにします.その直線ひとつひとつを頂点とします.

辺集合を次のように定めます.

$$\begin{array}{r}(L_i,L_j)\in E_{ij}\iff \text{2直線}{L}_i,L_j\text{の交点が}A\text{の元}\end{array}$$

いま,$K_3(D)=K_3(D{)}^{\mathrm{△}}\cup K_3(D{)}^{\bullet }$と分割できます.ただし,
$K_3(D{)}^{\mathrm{△}}$とは,
「三角形の頂点をなす3直線のうち,2直線を選んでその交点として得られる3つの格子点が$A$内のコーナーとなるような三角形の集合」で,

$K_3(D{)}^{\bullet }$とは,
「三角形の頂点をなす3直線の交点が$A$の1元集合であるような三角形の集合」
です.それぞれ非自明なコーナー,自明なコーナーに対応した三角形です.言いたいのは$K_3(D{)}^{\mathrm{△}}\ne \varnothing$でした.背理法で示します.

$K_3(D{)}^{\mathrm{△}}=\varnothing$を仮定すると,

$$\begin{array}{rl}& \mathrm{♯}{K}_3(D)=K_3(D{)}^{\bullet }=\mathrm{♯}A\le N^2\le {\delta }_{TRL}(\frac{\delta }{5})\cdot \mathrm{♯}{V}_1\cdot \mathrm{♯}{V}_2\cdot \mathrm{♯}{V}_3\end{array}$$
です.ただし最後の不等号は$N_{AS}$の定義と$N\ge N_{AS}$を用いました.さて,これは三角形除去補題の仮定であったので,3部グラフデータ$D^{\prime }=(V_1,V_2,V_3;E_{12}^{\prime },E_{23}^{\prime },E_{31}^{\prime })$が存在して$K_3(D^{\prime })=\varnothing$かつ任意の$(i,j)\in \{(1,2),(2,3),(3,1)\}$に対して
$$\begin{array}{r}\mathrm{♯}(E_{ij}\mathrm{\setminus }{E}_{ij}^{\prime })\le \frac{\delta }{5}・\mathrm{♯}{V}_i・\mathrm{♯}{V}_j\end{array}$$
です.各$E_{ij}\mathrm{\setminus }{E}_{ij}^{\prime }$に属する辺を除去するとき,$K_3(D{)}^{\bullet }$に属する三角形すべてから辺を一つずつ除去しなければなりません.これら$K_3(D{)}^{\bullet }$に属する三角形は2つの頂点(=2直線)から残りの1点が決まるので,どの2つも辺を共有することはあり得ません.(1辺を共有するならば同じ三角形なので)よって,除去すべき辺の個数は少なくとも$K_3(D{)}^{\bullet }$の元以上であり,

$$\begin{array}{r}{K}_3(D{)}^{\bullet }\le \sum _{i,j\in (1,2),(2,3)(3,1)}\mathrm{♯}(E_{ij}\mathrm{\setminus }{E}_{ij}^{\prime })\le \frac{\delta }{5}(5N^2-2N)<\delta N^2\end{array}$$
が成り立ちます.最後から2番目の不等号は$\mathrm{♯}{V}_1=N,\mathrm{♯}{V}_2=N,\mathrm{♯}{V}_3=2N-1$に注意し,$N\cdot N+N\cdot (2N-1)+(2N-1)\cdot N=5N^2-2N$より分かります.

$K_3(D{)}^{\bullet }=\mathrm{♯}A$だったので,結局$\mathrm{♯}A<\delta N^2$を得ますが,これは$\mathrm{♯}A\ge \delta N^2$に矛盾し,証明が完了します.

アイタイ・セメレディの定理$\Rightarrow$ロスの定理

実数$0<\delta \le 1$を任意にとって,$N_{Roth}=max\{N_{AS}({\delta }^2/5),\lceil 26/\delta \rceil \}$とする.$N\ge N_{Roth}(\delta )$とし,$\mathrm{♯}A\ge \delta N$を満たす$A\subset [N]$をとります.集合$B\subset [N{]}^2$を
$$\begin{array}{r}B=\{(x,y)\in [N{]}^2:x+2y\in A\}\end{array}$$
とします.
$x+2y=a$なる$(x,y)\in [N{]}^2$は$\lfloor \frac{a-1}{2}\rfloor$個あるので,
$$\begin{array}{rl}& \mathrm{♯}B\ge \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 }^2{N}^2}{4}-\frac{5\delta N}{4}-\frac{5}{4}\ge \frac{{\delta }^2{N}^2}{5}\end{array}$$
よって,アイタイ・セメレディの定理より,$B$はコーナー$\{(a,b),(a+c,b),(a,b+c)\}$を含みます.$(a,b\in {\mathbb{Z}}_{>0},c\in \mathbb{Z}\mathrm{\setminus }\{0\})$.このとき,$B$の定義より$A$は$\{a+2b,a+2b+c,a+2b+2c\}$を含むことが分かります.これは長さ3の等差数列.

感想

三角形除去補題$\Rightarrow$アイタイ・セメレディの定理の証明におけるグラフの作り方は見事ですね.次回はこれの一般化の証明を追っていきます.

謝辞

ここまで読んで下さりありがとうございました。誤植等指摘お願いいたします.