4
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.