セメレディの定理(有限形)

第1段階(有限な窓への帰着)。ある $d(A_0) > 0$ に対して無限の主張が成立せず、長さ $k$ の数列を一切含まないと仮定する。このとき任意の $N$ について、制限 $A_0 \cap [1,N]$ は $\{1,\dots,N\}$ の長さ $k$ 数列を含まない部分集合であり、そのサイズは固定された $\delta$ > 0 に対して $\delta$$N$ のように増加する。有限版が真であれば $N$ が任意に大きいときそのような族は存在し得ず矛盾する——ゆえに両者は同値である。

第2段階(正則分割)。$\{1,\dots,N\}$ 内の長さ $k$ の潜在的な数列を $(k-1)$-一様超グラフの辺とみなす。超グラフ正則化補題は頂点集合を有界個の部分に分割し、小さな例外部分を除いて、部分の任意の組が擬似ランダムになる:それらの間の辺密度はほぼ一定で、異常に密または疎な部分クラスタが存在しない。

第3段階(計数補題)。分割が正則であれば、対応する計数補題により、正の相対密度を持つ部分の組は期待される個数の完全な配置を含むことが示される——特に、長さ $k$ の数列が少なくとも1つ真に存在する。なぜなら正の密度を持つ正則な擬似ランダム構造は、検査対象のパターンを避けられないからである。

第4段階(除去論法)。もし $A$ が長さ $k$ の数列を全く含まないなら、計数補題により正則分割で数えられる配置のほとんどが退化することになり、それは $A$ からごくわずかな要素を取り除くだけですべての近似的な数列を消せることを意味する——これは $A$ がいくらでも大きな $N$ 上で密度 $\delta$ を保つことと矛盾する。したがって長さ $k$ の数列は存在しなければならない。(1977年のファーステンバーグによるエルゴード理論的証明と、ガワーズによる高次フーリエ解析的証明は、全く異なる道筋で同じ結論に達し、いずれも $N(k,\delta)$ について明示的だが天文学的に大きい評価を与える。)