セメレディの定理の組合せ論的証明ー１

Szemerédiの定理の証明は既に当ブログで解説済みです：

integers.hatenablog.com

しかしながら、Szemerédiの定理の証明は異なる分野の数学を用いて複数得られており、その中でも組合せ論的議論により証明したSzemerédiによるオリジナル証明に興味がありました。

その証明が簡単でないことを色々なところで目にしますが、Terence Taoが"Szemerédi's proof of Szemerédi's theorem"という、Szemerédiによるオリジナル証明を簡略化できるところは簡略化してまとめたunpublished noteを書いています。原論文ではなくこちらの方を勉強して当ブログに日本語で記録しておこうと思います(複数記事使います)。

記号設定

$\mathbb{N}=\{1, 2, 3, \dots \}$ .
$[N]:=\{1, 2, \dots, N\}$ for $N \in \mathbb{N}$ . ただし、便宜的に $[0]:=\emptyset$ とする。
$K \in \mathbb{N}$ に対して、 $K$ -APを $a \in \mathbb{Z}, r \in \mathbb{N}$ で

$\displaystyle \overrightarrow{P{ }} = a+r\cdot \overrightarrow{[K]}:=(a+kr)_{k \in [K]}=(a+r, a+2r, \dots, a+Kr)$

と表すことのできる組として定義する(ad hoc)。つまり、必ず単調増加に並べて考える。 $r=1$ のときは $a+\overrightarrow{[K]}$ , $a=0$ かつ $r=1$ のときは $\overrightarrow{[K]}$ と書く。
$K$ -AP: $\overrightarrow{P{ }}=a+r\cdot \overrightarrow{[K]}$ に対して、 $P \colon \mathbb{Z} \to \mathbb{Z}$ を $P(k):=a+kr$ と定義する。 $\overrightarrow{P{ }}=(P(1), \dots, P(K) )$ となっている。
$K$ -AP: $\overrightarrow{P{ }}=a+r\cdot \overrightarrow{[K]}$ が集合 $\mathbf{A}$ に含まれるとは $P([K]) \subset \mathbf{A}$ が成り立つときにいう。
$\overrightarrow{P{ }}$ がAPであるとは、或る $K \in \mathbb{N}$ が存在して $K$ -APであるときにいう(ad hoc)。このとき、 $\mathrm{len}(\overrightarrow{P{ }}):=K$ を $\overrightarrow{P{ }}$ の長さという。
AP全体のなす集合を $\mathcal{AP}$ とする。
集合 $\mathbf{E} \subset \mathbb{Z}$ と $h \in \mathbb{Z}$ に対して、 $h+\mathbf{E}:=\{h+n \mid n \in \mathbf{E}\}$ .
$X=O(Y)$ は或る絶対定数 $C$ に対して $\left|X\right| \leq CY$ が成り立つことの略記法。 $C$ がパラメータ依存するときは、例えば $k$ に依存するならば、 $X=O_k(Y)$ のように表す。
集合 $\mathbf{X}$ に対して、 $\mathbf{1}_{\mathbf{X}}$ は $\mathbf{X}$ の特性関数。つまり、 $x \in \mathbf{X}$ なら $\mathbf{1}_{\mathbf{X}}(x) = 1$ で、 $x \not \in \mathbf{X}$ であれば $\mathbf{1}_{\mathbf{X}}(x) = 0.$

Banach上漸近密度

$\mathbf{A} \subset \mathbb{Z}$ のBanch上漸近密度 $\overline{bd}(\mathbf{A})$ を

$\displaystyle \overline{bd}(\mathbf{A}) := \limsup_{N \to \infty}\max_{h \in \mathbb{Z}}\frac{\#\{\mathbf{A} \cap (h+[N])\}}{N}$

と定義する。

一般に、 $\overline{d}(\mathbf{A}) \leq \overline{bd}(\mathbf{A})$ が成り立つ( $\overline{d}(\mathbf{A})$ は $\mathbf{A}$ の上漸近密度)。

$\displaystyle \mathbf{A}:=\bigcup_{n \in \mathbb{N}}([n^3, n^3+n] \cap \mathbb{Z})$ とする。このとき、 $\overline{d}(\mathbf{A})=0$ であるが、 $\overline{bd}(\mathbf{A})=1$ である。

Szemerédiの定理

次の定理を証明するのが目的である。

定理 (Szemerédi, 1975)
$\mathbf{A} \subset \mathbb{N}$ が $\overline{bd}(\mathbf{A}) > 0$ を満たせば、 $\mathbf{A}$ は任意の $K \in \mathbb{N}$ に対して $K$ -APを含む。

integers.hatenablog.com

の無限版Szemerédiの定理と同値であることを証明しておく。

証明. 上漸近密度の不等式関係から、上記定理から無限版Szemerédiの定理が従う。無限版Szemerédiの定理が成り立つと仮定すると既に証明しているように有限版Szemerédiの定理(上記記事参照)が成り立つ。 $\mathbf{A} \subset \mathbb{N}$ を $\overline{bd}(\mathbf{A}) = \delta > 0$ を満たすような集合とする。正整数 $k$ を任意にとる。このとき、Banach上漸近密度の定義より