必ず見つかる等差数列 - カナンの数学ノート

T.Tao, A quantitiative ergodic theory proof of Szemerédi's theoremを読んでいきます。
ただでさえややこしい内容である上に全部英語なので、自分の中での理解を確かめるために学んだことをブログにまとめられたらな〜〜〜と思っております。

本記事はそのイントロダクションということで、↓の２つの定理を紹介します。

定理1.1: Van der Waerdenの定理
任意の自然数 $k,m\geqq 1$ に対して、ある自然数 $N=N_{vdW}(k,m) \geqq 1$ が存在して、任意の色づけ ${\mathbf c}:\{1,\dots , N\} \to \{1, \dots , m\}$ に対して同色で塗られた長さ $k$ の等差数列が存在する。

定理1.2: Szemerédiの定理
任意の自然数 $k\geqq 1$ と実数 $0 \lt \delta \leqq 1$ に対して、ある自然数 $N_{SZ}(k,\delta) \geqq 1$ が存在して、すべての $N\geqq N_{SZ}(k,\delta)$ に対して $A \subset \{1, \dots , N\}$ かつ $\frac{|A|}{N}\geqq \delta$ を満たす $A$ には長さ $k$ の等差数列が存在する。

すごそう(小並感)

Van der Waerdenの定理

厳密さを犠牲にしつつ、どんな定理なのかっていうのをざっくりと言い換えてみましょう。

定理1.1: Van der Waerdenの定理(言い換え)
人間「自然数を $m$ 色に塗り分けるよ！この中に同じ色で長さ $k$ の等差数列って存在するのかな…」
神「ある程度の長さ( $N_{vdW}(k,m)$ 以上)の自然数あれば必ず見つかるよ」
人間「マジ？」
神「マジ」

例

プログラムを組んで強引に調べたところ、
2色で塗り分けて長さ3の同色等差数列が存在するには、探す対象の自然数の最大値が9以上であれば必ず等差数列が発生することがわかりました。

1 2 3 4 5 6 7 8 9
この自然数を適当に2色で塗り分けてみます。
例えばこんな感じ。
1 2 3 4 5 6 7 8 9
この場合はここに同色の等差数列が存在しますね。
1 2 3 4 5 6 7 8 9
ここにもありますね。
1 2 3 4 5 6 7 8 9
こんな感じで、1〜9の数字をどんな風に２色で塗り分けたとしても、必ず長さ3の同色等差数列が発生します。*1
1〜9で等差数列が発生するわけだから、ましてや最大値が9より大きくても等差数列が発生しちゃうよね、ということになります。

これくらいならお手軽に実感できると思うので、皆さん是非1〜9の数字を2色に塗り分けてみてください。
必ず長さ3の同色等差数列が発生します。マジです。

さらに親しみやすく

さらにざっくりとさせると、次のような言い方ができるでしょう。

定理1.1: Van der Waerdenの定理(さらに言い換え)
自然数を $m$ 色に塗り分けると、同色で塗られた任意の長さの等差数列が存在する。

Szemerédiの定理

Van der Waerdenの定理では色の指定ができなかったのに対し、Szemerédiの定理では色を指定することができます。

こちらもざっくり言い換えるとこうなります。

定理1.2: Szemerédiの定理(言い換え)
人間「自然数のうち何%かだけ取り出したらその中に長さ $k$ の等差数列って存在するのかな…」
神「ある程度の長さ( $N_{SZ}(k,\delta)$ 以上)の自然数から取り出すなら必ず見つかるよ」
人間「マジ？」
神「マジ」
※ $5\%$ だけ取り出す場合は $\delta = 0.05$ と置く。つまり $0 \lt \delta \leqq 1$ となる。

もっと親しみやすくしましょう。

定理1.2: Szemerédiの定理(さらに言い換え)
自然数全体から $\delta$ の密度で取り出した集合には任意の長さの等差数列が存在する。
※ $0 \lt \delta \leqq 1$
※ 有限個取り出す場合は密度が0になってしまうため、条件を満たさないことに注意。

さすがにこれのプログラム検証は勘弁してください。