必ず見つかる等差数列
T.Tao, A quantitiative ergodic theory proof of Szemerédi's theoremを読んでいきます。
ただでさえややこしい内容である上に全部英語なので、自分の中での理解を確かめるために学んだことをブログにまとめられたらな〜〜〜と思っております。
本記事はそのイントロダクションということで、↓の2つの定理を紹介します。
任意の自然数
任意の自然数
すごそう(小並感)
Van der Waerdenの定理
厳密さを犠牲にしつつ、どんな定理なのかっていうのをざっくりと言い換えてみましょう。
人間「自然数を
神「ある程度の長さ(
人間「マジ?」
神「マジ」
例
プログラムを組んで強引に調べたところ、
2色で塗り分けて長さ3の同色等差数列が存在するには、探す対象の自然数の最大値が9以上であれば必ず等差数列が発生することがわかりました。
この自然数を適当に2色で塗り分けてみます。
例えばこんな感じ。
この場合はここに同色の等差数列が存在しますね。
ここにもありますね。
こんな感じで、1〜9の数字をどんな風に2色で塗り分けたとしても、必ず長さ3の同色等差数列が発生します。*1
1〜9で等差数列が発生するわけだから、ましてや最大値が9より大きくても等差数列が発生しちゃうよね、ということになります。
これくらいならお手軽に実感できると思うので、皆さん是非1〜9の数字を2色に塗り分けてみてください。
必ず長さ3の同色等差数列が発生します。マジです。
さらに親しみやすく
さらにざっくりとさせると、次のような言い方ができるでしょう。
自然数を
Szemerédiの定理
Van der Waerdenの定理では色の指定ができなかったのに対し、Szemerédiの定理では色を指定することができます。
こちらもざっくり言い換えるとこうなります。
人間「自然数のうち何%かだけ取り出したらその中に長さ
神「ある程度の長さ(
人間「マジ?」
神「マジ」
※
もっと親しみやすくしましょう。
自然数全体から
※
※ 有限個取り出す場合は密度が0になってしまうため、条件を満たさないことに注意。
さすがにこれのプログラム検証は勘弁してください。
SzemerédiからVan der Waerdenへ
色の指定ができるということから、Szemerédiの定理はVan der Waerdenの定理よりすごいということがわかります。
もうちょっと数学的にいうと、Szemerédiの定理はVan der Waerdenの定理を包含する、ということです。
大雑把な証明
$$
N_{vdW}(k,m) := N_{SZ}\left(k,\frac{1}{m}\right)
$$と置けばいいらしいです。どういうことでしょうか。
改めて確認しますが、
目標
自然数を色で塗り分けたときに、同色で長さ
の等差数列が発生することを示したい
願わくばどれだけの自然数があれば十分であるかというのが知りたい
使えるもの
Szemerédiの定理
です。
実はこれはそんなに難しいことでは無く、次のような考え方で示せます。
- ひとまず
から
を
色で塗り分ける。
- 鳩ノ巣原理より、密度
で塗られた色が必ず存在する。
- Szemerédiの定理より、その密度で塗られた色の中に長さ
の等差数列が存在する。(
とすれば良さげ)
- おわり。
まとめと今後のおはなし
ひとまずはSzemerédiの定理の証明を行うことを目標に進めますが、むしろ本当の目的はその先にあるGreen-Taoの定理です。
素数のみから構成される任意の長さの等差数列が存在する。
自然数全体に対する素数の密度はであるため、Szemerédiの定理をもってしてもこの定理をそのまま導くことはできません。
じゃあどうすればいいんだよ!!ということの研究がSzemerédiの定理の理解の先に広がっているようです。
非常にたのしみ
先に謝辞をば
Green-Taoの定理を知るキッカケであり、ブログで論文の全解説をしていただいたせきゅーんさんに感謝します。
integers.hatenablog.com
英語がてんでダメなので論文を読むときはINTEGERS開きっぱなしです。ホントにありがとうございます。
*1:長さ8では発生せず、実際に反例があります。例えば、1 2 3 4 5 6 7 8という塗り分けを行った場合、長さ3の同色等差数列は存在しません。