ファン・デル・ヴェルデン数

van der Waerdenの定理

における $N(k, m)$ の取り得る最小の値をvan der Waerden数といい、 $W(k, m)$ と表します。

$W(k, 1)=k, \quad W(2, m)=m+1$

はすぐに分かります。それ以外に確定しているのは

$\begin{align}&W(3, 2)=9, \ W(4, 2)=35, \ W(5, 2)=178, \ W(6, 2)=1132,\\ &W(3, 3)=27, \ W(4, 3) = 293,\\ &W(3, 4)=76\end{align}$

のみです(このうち $293$ は素数)。

一般的な上界についてはGowers(フィールズメダリスト)によるものがbestのようです：

定理 (Gowers, 2001) $\ \ \ W(k, m) < 2^{2^{m^{2^{2^{k+9}}}}}.$

特に、 $m=2$ の場合は $W(k, 2) < 2^{2^{2^{2^{2^{k+9}}}}}$ が示されていることになりますが、次のような予想があります：

Grahamの1000ドル予想 $\ \ \ W(k, 2) \leq 2^{k^2}.$

INTEGERS