Is Van der Waerden's function elementary

Question

Van der Waerden's function was proved to have elementary upper bound on growth rate.

Is the Van der Waerden's function itself elementary in the sense of Kalmar?

Answer 1

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$.