定理証明済み

セメレディの定理

内容

正の上密度（ $\limsup_{N\to\infty} |A \cap [1,N]|/N > 0$ ）を持つ任意の部分集合 $A \subseteq \mathbb{N}$ は、任意の長さの等差数列を含む。すなわち任意の $k \ge 1$ と $\delta > 0$ に対し $N(k,\delta)$ が存在して、 $N \ge N(k,\delta)$ のとき $\{1,\dots,N\}$ の要素数 $\delta N$ 以上の任意の部分集合は $k$ 項の等差数列を含む。

なぜ正しいのか?

整数の部分集合が全体の中で一定の正の割合を占めていれば、等間隔のパターンを永遠に避け続けることはできない——選んだ数をどのように散らそうとしても、望む長さの等差数列が必ずどこかに現れる。密度だけで算術的な構造が強制されるのである。

証明の概略

密度 $\delta$ の集合 $A \subseteq [1,N]$ は、擬似ランダムに振る舞うか（その場合は期待されるおよそ $\delta^k N^2$ 個の $k$ 項等差数列を含む）、さもなければ擬似ランダム性が崩れて構造的な配置と $A$ が相関を持ち、 $A$ の密度が真に大きい $\delta + c(\delta)$ となる部分等差数列へと移ることができる。密度は1を超えられないため、この密度増加の反復は有限回で停止せざるを得ない。構造部分と擬似ランダム部分への分解は、セメレディの正則性補題（後の別証明では高次フーリエ解析、エルゴード理論、あるいはハイパーグラフ正則性）によって与えられる。

証明者

1975年に証明エンドレ・セメレディ

この定理を使うトピック

セメレディの定理

参考文献

Endre Szemerédi (1975). On sets of integers containing no k elements in arithmetic progression