セメレディの定理(1974年)

4項の等差数列まで拡張し、ついに一般の主張にまで拡張した（エルデシュ・テュラン問題の解決）

組み合わせ論に基礎を置いた証明で、ファン・デル・ヴェルデンの定理を用いている

フルステンベルクの証明(1977年)

エルゴート理論に基礎を置いた証明はさらにいくつかの拡張をもたらした

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

ファン・デル・ヴェルデンの定理の有限版が、

任意の整数k,lに対して、N(k,l)が存在し、N＞N(k,l)かつ{1,2,・・・,N}がｌこの色に塗り分けられていたら、必ず単一色のk項の等差数列が存在する

ファン・デル・ヴェルデンの証明が与えるN(k,l)の上界は非常に大きい

セメレディの定理は定量的評価ではなく、意味のある上界を与えないが、ガワーズはある定数ｃについて

r(N)＜N/(loglogN)^c

を示した。

もし、

r(N)＜N/(logN)^c

が成り立てば素数の集合Ｐはいくらでも長い等差数列を含むことになる

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝