【§2】ひとまずSzemerédiの定理へ
*4/25追記:一部の議論を追加、修正しました。
§2 The finite cyclic group settingを読んでいきます。
前回は定義をたくさんして議論の準備ができました。
canaan1008.hatenablog.com
そして、今回のテーマとなる定理はこちら!ババン
任意の整数
\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
$$が成立する。
というかこの論文、「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の仮定を満たすようなものをうまいこと組み立てていきます。
任意の整数
\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の定理の証明に用いたい
定理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の証明が始まります。
ちなみにこちらも突然別の定理(証明はさらに後回し)が降ってきてそこから証明を行うという方法です。