[Van der Waerden's](http://en.wikipedia.org/wiki/Van_der_Waerden%27s_theorem) function was [proved](https://www.dpmms.cam.ac.uk/~wtg10/sz898.dvi) to have elementary upper bound on growth rate. 


Is the Van der Waerden's function itself [elementary](http://en.wikipedia.org/wiki/ELEMENTARY) in the sense of Kalmar?



Is Van der Waerden's function elementary
Yes, this should follow from the elementary bound. The point is that having a Kalmar elementary time bound is "closed under" searches through exponentially large collections.


Suppose $N=W(r,k)$ is least such that if the integers $\{1, 2, \dots, N\}$ are colored, each with one of $r$ different colors, then there are at least $k$ integers in arithmetic progression all of the same color.


Say we have an elementary upper bound $b$ on $N$. Then starting with $n=0$ we just try all $n\le b$, try all possible colorings ($r^n$ many) try all possible $k$-tuples (less than $n^k$ many) and check whether they are same-colored and in arithmetic progression. Once we have an $n$ such that for all colorings we have found such a progression, then $n=N$.


