グリーン・タオの定理2 証明の流れ
こんにちは,itouです.今回はグリーン・タオの定理(著:関真一朗)(郎ではなく朗！)第２章の解説の続きです.前回の記事は こちら .
グリーン・タオの定理に至るまで
前回示したグラハム・ロスチャイルドの定理の特殊な場合であるファン・デル・ヴァルデンの定理とは以下の命題でした.(正確にはグラハム・ロスチャイルドの定理の$d=1$の場合が有限版ファン・デル・ヴァルデンの定理で,これがファン・デル・ヴァルデンの定理に同値)
正整数全体の集合を有限個の部分集合に分割するとき,それらのうち少なくとも一つの部分集合は任意の長さの等差数列を含む.(ただし分割と呼ぶときはどの部分集合も共通部分が空集合である)
そしてファン・デル・ヴァルデンの定理は等差数列がどの部分集合に含まれているか教えてくれないという欠点があるのでした.この欠点を克服するための拡張がセメレディの定理です.
$A\subset \mathbb Z_{>0}$における上密度$\overline{d}(A)$を
\begin{align}
\overline{d}(A)=\limsup_{N\rightarrow \infty}\frac{\sharp (A\cap [N])}{N}
\end{align}
とする.
※$\limsup$は上極限のこと.
$A\subset \mathbb Z_{>0}$が$\overline{d}(A)>0$を満たすとき,$A$は任意の等差数列を含む.
セメレディの定理は任意の長さの等差数列を含むための十分条件を与えてくれるという意味でファン・デル・ヴァルデンの定理の拡張になっています.さらなる拡張も紹介しましょう.
$A\subset \mathbb Z_{>0}$における上密度$\overline{d^*}(A)$を
\begin{align}
\overline{d^*}(A)=\limsup_{N\rightarrow \infty}\max_{h\in \mathbb Z_{>0} }\frac{\sharp (A\cap ([N]+h))}{N}
\end{align}
とする.
$A\subset \mathbb Z_{>0}$が$\overline{d^*}(A)>0$を満たすとき,$A$は任意の等差数列を含む.
バナッハ上密度と上密度について,一般に$ \overline{d}(A) \leq\overline{d^*}(A)$です.そのため任意の長さの等差数列を含むための十分条件がさらに緩くなっています.
しかし残念ながら,$\overline{d^*}(\mathbb P)=0$なのです!素数の集合とはそれほどに疎なのです.つまりバナッハ上密度版セメレディの定理からグリーン・タオの定理を導くことはできません.しかし,ここまでの流れを見れば,「よい密度」を定義してやればよいと予測されます.それが擬ランダム測度(第5章)です.
さらにもう1つ紹介します.
正整数$k$と実数$0<\delta \leq1$に対して,正整数$k$が存在して,以下が成立する.$N\geq N_{ST}(k,\delta)$を満たす任意の整数$N$に対して,$\sharp A\geq \delta N$であるような集合$A\subset [N]$は長さ$k$の等差数列を含む.
有限版セメレディの定理
$\Rightarrow$バナッハ上密度版セメレディの定理
$\Rightarrow$セメレディの定理
という関係があるので有限版から考えたいということです.
なお,グリーン・タオの定理は素数セメレディの定理において$A=\mathbb P$としたものですが,
有限版素数セメレディの定理
$\Rightarrow$素数セメレディの定理
$\Rightarrow$グリーン・タオの定理
という関係です.
さて,本書ではAPラムゼー問題を$d$次元に一般化して議論が進んでいきます.
$S$を$\mathbb Z^d$の有限部分集合とする.$a\in \mathbb Z^d $および$l\in \mathbb Z_{>0}$を用いて
\begin{align}
a+lS=\{a+ls:s\in S\}
\end{align}
と表される$\mathbb Z^d$の部分集合を「形状が$S$であるような星座」といい,「$S$星座」と略す.部分集合$A\subset \mathbb Z^d$が「$ \mathbb Z^d$の任意の有限部分集合に対して$A$は$S$星座を少なくとも1つ含む」という条件を満たすとき,「$A$は$\mathbb Z^d$における任意の形状の星座を含む」という.
星座はグラハム・ロスチャイルドの定理に登場した等差数列の一般化とは異なる方向への一般化であることに注意して下さい.(星座という訳はロマンチックですね)
この多次元の等差数列,改め星座についても同様の定理が成り立ちます.
$A\subset \mathbb Z^d$の$\mathbb Z^d$ における上密度$\overline{d_{\mathbb Z^d}}(A)$を
\begin{align}
\overline{d_{\mathbb Z^d}}(A)=\lim_{N\rightarrow \infty}\sup\frac{\sharp (A\cap [-N,N]^d)}{\sharp [-N,N]^d}
\end{align}
とする.
$A\subset \mathbb Z^d$が$\overline{d_{\mathbb Z^d}}(A)>0$を満たすとき,$A$は$ \mathbb Z^d $における任意の形状の星座を含む.
$A\subset \mathbb Z^d$の$\mathbb Z^d$ におけるバナッハ上密度$\overline{d^*_{\mathbb Z^d}}(A)$を
\begin{align}
\overline{d^*_{\mathbb Z^d}}(A)=\limsup_{N\rightarrow \infty}\max_{h\in \mathbb Z^d} \frac{\sharp (A\cap ([N]^d+h))}{N^d}
\end{align}
とする.
$A\subset \mathbb Z^d$が$\overline{d^*_{\mathbb Z^d}}(A)>0$を満たすとき,$A$は$ \mathbb Z^d $における任意の形状の星座を含む.
$\mathbb Z^d $の部分集合$S$と実数$0<\delta \leq1$に対して,正整数$N_{MST}(d,S,\delta)$が存在して,以下が成立する.$N\geq N_{MST}(d,S,\delta)$を満たす任意の整数$N$に対して,$\sharp A\geq \delta N^d$であるような集合$A\subset [N]^d$は$S$星座を含む.
以上述べた7つの定理のうち最も強いのが有限版多次元セメレディの定理です.さらに有限版多次元セメレディの定理はハイパーグラフ除去補題によって示されます.実際は
ハイパーグラフ除去補題
$\Rightarrow$多次元コーナー定理
$\Rightarrow$有限版多次元セメレディの定理
という流れで示されます.
次回はこの流れを特殊化したもの,
三角形除去補題
$\Rightarrow$アイタイ・セメレディの定理(コーナー定理ともいう)
$\Rightarrow$ロスの定理
を三角形除去補題を認めた上で見ていきましょう.
感想
次回からグラフの話をします.離散数学初めてやるかも
謝辞
ここまで読んで下さりありがとうございました。誤り等の指摘よろしくお願いいたします。
参考文献
この記事を高評価した人
この記事に送られたバッジ
投稿者
