van der Warden数とその仲間たちの評価

昨日までに述べた，van der Waerdenの定理
「任意の正整数$l$, $r$に対して正整数$N(l,r)$が存在して，$\mathrm{\forall }C:[1,N(l,r)]\to [1,r]$に対して正整数$a,d$が存在して，$C(a+xd)$, $x=1,\dots ,l$は一定値」，
Graham-Rothschildの定理
「任意の正整数$l$, $r$に対して，或る$N(l,m,r)$が存在して次を満たす：任意の$C:[1,N(l,m,r)]\to [1,r]$に対して，或る$a,d_1,\dots ,d_m(>0)$が存在して，$C(a+\sum _{i=1}^m{x}_i{d}_i)$は，$[1,l{]}^m$の各$l$同値類上で定数」
は，つまるところ，十分長い区間$[1,N]$ならば，どのように塗り分けても，同じ色になってしまう長い等差数列がある（$l$同値類がある），ように$N$を取ることができる，ということだった．

すると次は，$N(l,r)$や$N(l,m,r)$がどのくらいの大きさの数になるのか（十分長い区間の長さはどれくらいか？），が気になってくる．正整数$l$, $r$について，van der Waerdenの定理が存在を保証するような$N(l,r)$の内最小の数を$W(l,r)$と書く．この数の上からの評価については面白い経緯があったようで，それをSaharon Shelah, Primitive recursive bounds for van der Waerden numbers, J. Amer. Math. Soc. 1 (1988), 683-697, から抜き書きしておく．

1970年代に，Solovayは$W(l,r)$が本質的にAckermann関数と同じぐらい速く大きくなることを示す（よって$W(l,r)$は原始帰納的関数で無いこと，同時に，van der Waerdenの定理の証明には二重帰納法が必須である事を示す）ための研究プログラムを提唱した．一方そのプログラムが遂行可能である事に疑念を示す研究者もいた（KrieselやMacIntyre）し，それどころか，Grahamのように，$W(l,r)$が原始帰納的でないという主張に同意しない研究者もいた．

結局，上の論文でShelahは，Grahamが言うように$W(l,r)$は原始帰納的関数であること，並びに，関連する他の問題（Hales-Jewettの定理，Graham-Rothschildの定理，Affine Ramsey定理）に現れる定数についても同様である事を示した．

Shelahは最初，Solovayが言うように$W(l,r)$は原始帰納的関数ではない，と思っていが，結局Grahamのほうが正しかった，と書いている．「定理は成立を信じるものによってのみ証明される」，とよくいうが，このようなことがあるので，一概には言えないようである．

原始帰納的関数やAckermann関数については，藤田さんの「なげやりアカデミア」に「原始帰納的函数とアッカーマン函数」という文書があり大変参考になる．