【§2】ひとまずSzemerédiの定理へ

*4/25追記：一部の議論を追加、修正しました。
§2 The finite cyclic group settingを読んでいきます。

前回は定義をたくさんして議論の準備ができました。
canaan1008.hatenablog.com

そして、今回のテーマとなる定理はこちら！ﾊﾞﾊﾞﾝ

定理2.4 定量的回帰定理
任意の整数、十分大きな素数、任意のに対し、
を満たす任意の非負値有界関数に対して、$$
\mathbb{E}_{r\in\mathbb{Z}_N}\left(\int_{\mathbb{Z}_N}\prod_{j=0}^{k-1}T^{jr}f\right) \gg_{k,\delta} 1
$$が成立する。

この定理自体の証明は後回しにしますが、この定理が成り立つとするとそこからSzemerédiの定理を導くことができます。

というかこの論文、「Aが成り立つとするとBが成り立つよ！Aの証明はあとでやるから」ってスタンスで進んでいくようです。

成り立つなら成り立つ

定理2.4Szemerédiの定理 の証明をします。

を固定、を十分大きな整数とし、がを満たすと仮定する。
ベルトランの仮説より、を満たす素数が存在する。
ここで射影に対して、を$$
\iota := pr_{N'}\mid_{\{1,\dots, N\}}
$$と定めると、これは単射となる。の元に対する写像の像をとする。

このとき、\begin{align}
\int_{\mathbb{Z}_{N'}}\mathbb{1}_{A'}&=\mathbb{E}_{\mathbb{Z}_{N'}}\mathbb{1}_{A'}\\
&=\frac{|A'|}{N'}\\
&=\frac{|A|}{N'}\\
&\gt \frac{|A|}{2kN}\\
&\geqq \frac{\delta N}{2kN}\\
&=\frac{\delta}{2k}
\end{align}なので、定理2.4の仮定を満たしているため$$
\mathbb{E}_{r\in\mathbb{Z}_{N'}}\left(\int_{\mathbb{Z}_{N'}}\prod_{j=0}^{k-1}T^{jr}\mathbb{1}_{A'}\right)\gg_{k,\delta}1
$$が成り立つ。

これより、\begin{align}
\frac{1}{N'}\sum_{r=1}^{N'}\frac{1}{N'}\sum_{x=1}^{N'}\prod_{j=0}^{k-1}T^{jr}\mathbb{1}_{A'}(x) &\gg_{k,\delta}1\\
\frac{1}{(N')^2}\sum_{r=1}^{N'}\sum_{x=1}^{N'}\prod_{j=0}^{k-1}T^{jr}\mathbb{1}_{A'}(x) &\gg_{k,\delta}1\\
\sum_{r=1}^{N'}\sum_{x=1}^{N'}\prod_{j=0}^{k-1}T^{jr}\mathbb{1}_{A'}(x) &\gg_{k,\delta}(N')^2\\
\sum_{r=1}^{N'}\sum_{x=1}^{N'}\prod_{j=0}^{k-1}\mathbb{1}_{A'}(x+jr) &\gg_{k,\delta}(N')^2\tag{1}
\end{align}*1

ここで$$
\prod_{j=0}^{k-1}\mathbb{1}_{A'}(x+jr)=\begin{cases}
1&(\underbrace{x,x+r,\dots, x+(k-1)r}_{k\text{個}} \in A')\\
0&\text{otherwise}
\end{cases}
$$であることから、(1)式は$$
\left|\left\{(x,r)\in\mathbb{Z}_{N'}^2\mid x,x+r,\dots, x+(k-1)r \in A'\right\}\right|\gg_{k,\delta}(N')^2\tag{2}
$$と同値。

の個数((2)の左辺におけるの個数)は高々個
が十分大きければ、(2)よりである長さの等差数列
がに含まれる。

は単射なので、に対してが定まり、より$$
1\leqq a \leqq N
$$を満たす。
また、とすれば、であるための範囲と合わせると$$
-N \lt d\lt N
$$
ここでを満たすについて、を考える。
の範囲より、は$$
-(k-1)N\lt a+jd \lt kN
$$を満たす。

なので、とすると、$$
a+jd\equiv c_j \pmod{N'}\tag{3}
$$であることからより\begin{align}
-kN\lt a+jd-c_j &\lt kN\\
|(a+jd)-c_j| &\lt kN
\end{align}より$$
|(a+jd)-c_j| \lt N'
$$これと(3)より、$$
a+jd=c_j
$$であることから、となる。

すなわち、が含む初項、公差、項数の等差数列に対する初項、公差、項数の等差数列がに含まれることが示された。

軽く解説

仮定を満たすために

証明の中では、\begin{align}
k:\ &\text{見つけたい等差数列の長さ}\\
A:\ &\text{等差数列を探し出したい集合}(A\subset \{1,\dots, N\})\\
\delta:\ &\{1,\dots, N\}\text{に対する}A\text{の密度}\\
N:\ &\text{整数(今回は素数とは限らないことに注意)}
\end{align}として考えています。
Szemerédiの定理の仮定として用いられているこれらの記号を使って、定理2.4の仮定を満たすようなものをうまいこと組み立てていきます。

定理2.4(再掲) 定量的回帰定理
任意の整数、十分大きな素数、任意のに対し、
を満たす任意の非負値有界関数に対して、$$
\mathbb{E}_{r\in\mathbb{Z}_N}\left(\int_{\mathbb{Z}_N}\prod_{j=0}^{k-1}T^{jr}f\right) \gg_{k,\delta} 1
$$が成立する。

定理2.4の仮定では、整数、素数、非負値有界関数、密度が必要になります。
Szemerédiの定理の証明に用いたいを用いてこれらを作ると、次のようにすれば良いでしょう。

定理2.4の仮定	新しく作ると…
整数	(そのまま)
素数	を満たす素数
非負値有界関数	(はをに埋め込んだもの)
密度

※表の左側は定理2.4の値、右側は証明中の値であることに注意！

これらの置き換えを行うことで定理2.4の仮定をうまいこと満たすため、$$
\mathbb{E}_{r\in\mathbb{Z}_{N'}}\left(\int_{\mathbb{Z}_{N'}}\prod_{j=0}^{k-1}T^{jr}\mathbb{1}_{A'}\right)\gg_{k,\delta}1
$$が成り立つというわけです。

等差数列発見器

特性関数の定義から、に対して、$$
T^{jr}\mathbb{1}_{A'}(x)=\mathbb{1}_{A'}(x+jr)=\begin{cases}
1&(x+jr\in A')\\
0&(x+jr\notin A')
\end{cases}
$$が成り立ちます。
がに含まれていれば、含まれていなければです。

ここでをからまで動かすと、がに含まれているか含まれていないかでかの値を取るわけですが、それらを全て掛け合わせることで、に関して

がに全て含まれていれば
一つでも含まれていなければ
を得ることができます。
初項が、公差が、長さがの等差数列がに含まれているかどうかがわかるというわけです。すごい！

をそれぞれで動かして、長さの等差数列が含まれているかどうかでの値を取るわけですから、$$
\sum_{r=1}^{N'}\sum_{x=1}^{N'}\prod_{j=0}^{k-1}\mathbb{1}_{A'}(x+jr)\gg_{k,\delta}(N')^2
$$の左辺は長さの等差数列を何本含んでいるか、というのを表しています。つまり、$$
\left|\left\{(x,r)\in\mathbb{Z}_{N'}^2\mid x,x+r,\dots, x+(k-1)r \in A'\right\}\right|\gg_{k,\delta}(N')^2
$$という置き換えができるわけです。

で持ち上げて

もうちょっと式をわかりやすく読み替えると、$$
(A'\text{内にある初項}x,\text{公差}r, \text{長さ}k\text{の等差数列の本数})\gg_{k,\delta}(N')^2\tag{3}
$$となります。

ただ…のときは公差0ですから等差数列とは言い難いですね。
いや厳密には等差数列かもしれないんですが、というのを探したいんじゃないんです。
しかーし！であることから、あったとしても高々本です。

ここで改めて(3)式を見ると、長さの等差数列の本数は(の定数倍)本以上あることを示しています。
の等差数列()があったとしても高々本ですので、を十分大きく取るとにはの長さの等差数列を必ず含む必要がでてきます。

対応する等差数列

さて、このようにして等差数列が見つかったわけですが、これは内で等差数列が見つかっただけに過ぎません。
本当に探したかったのはの範囲内なのです……

とりあえずなので、の値を内で見つかりそうな数列の初項としましょう。
そしてでもあるので、の値を内で見つかりそうな数列の公差を使ってとしましょう

ここでに対してであれば万々歳なんですが、そうなる保証はありません。世知辛い。
はおろか、に入らない可能性だってあります。

ただ、によるの射影はとなります。(より)
そして、に対するの写像を考えると、であることからとなり、の中に入ってきます。この値をとしましょうか。
すると、の世界に行ってすぐ帰ってきたのですから、出発したときの値と帰ってきたときの値が異なったとしても、を法として合同になるはずです。

ところで、値の範囲を考えると$$
|(a+jd)-c_j|\lt N'
$$であることがわかります。(の値の範囲と、であることから計算できます。)
つまり、との距離はより小さい、ということを得ます。
2つの値はを法として合同であることも加味するとこの2つは等しい値、つまりでなければならないという結論になります*2。

このことからの値はどうあがいてもの中に含まざるを得ないため、の中に等差数列が含まれる、ということになります。

今後

とりあえず定理2.4が成り立つならSzemerédiの定理は成り立つようだけど、そもそも定理2.4が成り立つかどうかがわかんないじゃん！
ということでこのあとは定理2.4の証明が始まります。

ちなみにこちらも突然別の定理(証明はさらに後回し)が降ってきてそこから証明を行うという方法です。

*1:の定義、つまりの定義はとによらない定数の積で上から押さえられるので、このように右辺への移項のようなことができるわけです。定数でいくらでも右辺の値は調整できるのでひとまずと書いていたけど、素数によらず成り立たせなければいけないため右辺のを消すことはできないよ〜〜ってことです。

*2:完全に余談ですがという結論を自分の手で導いたとき、あたかも推理小説の探偵になった気分でした。2人は同一人物であるという決定的な証拠を突きつけたような、そんな感じ。