Szemerédiの定理の証明は既に当ブログで解説済みです:
しかしながら、Szemerédiの定理の証明は異なる分野の数学を用いて複数得られており、その中でも組合せ論的議論により証明したSzemerédiによるオリジナル証明に興味がありました。
その証明が簡単でないことを色々なところで目にしますが、Terence Taoが"Szemerédi's proof of Szemerédi's theorem"という、Szemerédiによるオリジナル証明を簡略化できるところは簡略化してまとめたunpublished noteを書いています。原論文ではなくこちらの方を勉強して当ブログに日本語で記録しておこうと思います(複数記事使います)。
記号設定
.
for
. ただし、便宜的に
とする。
に対して、
-APを
で
と表すことのできる組として定義する(ad hoc)。つまり、必ず単調増加に並べて考える。のときは
,
かつ
のときは
と書く。
-AP:
に対して、
を
と定義する。
となっている。
-AP:
が集合
に含まれるとは
が成り立つときにいう。
がAPであるとは、或る
が存在して
-APであるときにいう(ad hoc)。このとき、
を
の長さという。
AP全体のなす集合をとする。
集合と
に対して、
.
は或る絶対定数
に対して
が成り立つことの略記法。
がパラメータ依存するときは、例えば
に依存するならば、
のように表す。
集合に対して、
は
の特性関数。つまり、
なら
で、
であれば
Szemerédiの定理
次の定理を証明するのが目的である。
の無限版Szemerédiの定理と同値であることを証明しておく。
証明. 上漸近密度の不等式関係から、上記定理から無限版Szemerédiの定理が従う。無限版Szemerédiの定理が成り立つと仮定すると既に証明しているように有限版Szemerédiの定理(上記記事参照)が成り立つ。 を
を満たすような 集合とする。 正整数
を任意にとる。 このとき、Banach上漸近密度の定義より
を満たすような整数が存在する。
が成り立つようなをとる。 すると、
が成り立つので、有限版Szemerédiの定理よりは長さ
の等差数列を含む。 このとき、
も長さ
の等差数列を含む。 Q.E.D.