セメレディの定理

この有限版は単純なコンパクト性の議論によって無限密度の主張と論理的に同値であり、実際に証明されるのはこの形である:無限集合ひとつの代わりに、大きいが有限な窓の中の有限個の配置だけを制御すればよい。

第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)$ について明示的だが天文学的に大きい評価を与える。)

これはセメレディの定理の最初の非自明な場合であり、一般の $k$ に必要な重い正則化機構の代わりにフーリエ解析を用いて1953年にロスによって証明された。彼の「密度増加」戦略——パターンを見つけるか、集合が予想外に構造化されていることを示してより密な部分数列に移るか——は、後にはるかに洗練された形で一般定理とグリーン・タオ定理に再利用される設計図となった。

第1段階(フーリエによる数列の計数)。$A \subseteq \{1,\dots,N\}$ が密度 $\delta$ を持ち、非自明な3項数列を持たないと仮定する。$A$ の指示関数のフーリエ変換を $\hat{1_A}(\theta) = \sum_{n \in A} e(\theta n)$ と書くと、三つ組 $(x, x+r, x+2r) \in A^3$ の個数は $\theta$ についての $\hat{1_A}(\theta)^2 \, \overline{\hat{1_A}(2\theta)}$ の積分として書ける。

第2段階(擬似ランダムな場合)。$1_A$ のゼロでないすべてのフーリエ係数が $\delta^2$ に比べて小さければ、積分は $\theta = 0$ の項だけに支配され、これだけでおよそ $\delta^3 N^2$ 個の三つ組——自明なものよりはるかに多い——が強制され、$A$ に三つ組がないという仮定と矛盾する。

第3段階(密度増加)。したがってあるゼロでない係数が大きいはずであり、これは $1_A$ が線形位相 $e(\theta n)$ と相関することを意味する。つまり $A$ はある等差数列(またはボーア集合)上で顕著に偏っている。その部分数列に制限すると、$A$ の密度が一定の乗法因子だけ増加した短い区間が得られる。

第4段階(反復と結論)。密度は1を超えられないので、この密度増加ステップを有限回繰り返せば過程は終了しなければならない——つまり最終的に第2段階の擬似ランダムな場合が強制され、欠けていた3項数列が得られ、数列が存在しないという仮定と矛盾する。ロスの元の評価は $N(3,\delta) \lesssim \exp(\exp(1/\delta))$ 型のしきい値を与える。これは数十年かけて改良され、2023年のケリーとメカの議論はベーレンドの古典的構成に近い、密度 $N(3,\delta) \lesssim \exp\!\big(-c(\log N)^{1/12}\big) N$ 型までこの場合のギャップをほぼ閉じた。