ファン・デル・ヴェルデンの定理(1927年) 自然数を２組(または任意の有限個の組)に分けたとき、少なくとも１組は任意に長い等差数列を含む

エルデシュ・テュラン予想(1936年)

正の密度を持つような任意の自然数列は任意の長さの等差数列を含む

ファン・デル・ヴェルデンの定理を含む予想である。セメレディにより解決された。

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

1,2,3,・・・,Nの部分列で、長さkの等差数列を含まないものを考えるとき、部分列の元の個数の最大値をAk(N)とする。

ｋを一つ固定するとき、Ak(N)/N→0 (N→∞)が成立する。

セメレディの定理は定量的にみると最低限の評価であり、これを解決する問題は大きなｋに対しては依然として未解決であった。

ガワーズの定理

k=4の場合に、A4(N)/N≦(loglogN)^-c (N→∞)が成立する。

この手法を任意のｋに拡張すれば,

Ak(N)/N≦(loglogN)^-c(k) (N→∞)を証明できそうである。

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