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?

4

$\begingroup$
$\endgroup$

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?

5

$\begingroup$
$\endgroup$

Yes, this should follow from the elementary bound. The point is that to 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$.